# 1425. Constrained Subsequence Sum

## Problem Statement

\
Given an integer array `nums` and an integer `k`, return the maximum sum of a **non-empty** subsequence of that array such that for every two **consecutive** integers in the subsequence, `nums[i]` and `nums[j]`, where `i < j`, the condition `j - i <= k` is satisfied.

A *subsequence* of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [10,2,-10,5,20], k = 2
</strong><strong>Output: 37
</strong>Explanation: The subsequence is [10, 2, 5, 20].
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [-1,-2,-3], k = 1
</strong><strong>Output: -1
</strong>Explanation: The subsequence must be non-empty, so we choose the largest number.
</code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [10,-2,-10,-5,20], k = 2
</strong><strong>Output: 23
</strong>Explanation: The subsequence is [10, -2, -5, 20].
</code></pre>

&#x20;

**Constraints:**

* `1 <= k <= nums.length <= 105`
* `-104 <= nums[i] <= 104`

## Intuition

```
```

### Links

<https://leetcode.com/problems/constrained-subsequence-sum/description/>

### Video Links

<https://www.youtube.com/watch?v=tWhboGihflM&ab_channel=codestorywithMIK>

### Approach 1:

```
DP : Memoization
We take, not_take maintain a prev variable, and do accordingly
,
Here prev is -1 so gives Seg fault with vector memoize, dont waste time use map
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    unordered_map<string, int> mp;
    int find_ans(int prev, int index, vector<int>& nums, int k){
        if(index == nums.size())
            return 0;

        string key = to_string(prev) + "_" + to_string(index);
        if(mp.find(key) != mp.end())
            return mp[key];
        int ans = 0;
        if(prev == -1 or index-prev <= k){
            int take = nums[index]+find_ans(index, index+1, nums, k);
            int not_take = find_ans(prev, index+1, nums, k);

            ans = max( take, not_take);
        }

        return mp[key] = ans;
    }

    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        int val = find_ans(-1, 0, nums, k);
        if(val == 0)
            return *max_element(nums.begin(), nums.end());
        return val;
    }
};
```

{% endcode %}

### Approach 2:

```
Bottom UP:
We do like LIS approach
Maintain dp max and decide for ith point based on jth point

At each step from i, we go from i-1 to 0, till i-j<=k
Compute at each step max
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp = nums;

        int ans = dp[0];
        for(int index=1; index<n ; index++){
            for(int prev=index-1; prev>=0 and index-prev<=k; prev--){
                dp[index] = max(dp[index], nums[index]+dp[prev]);
            }
            ans = max(ans, dp[index]);
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 3:

```
Heap + DP
Here the issue is that we are going from i-1 to 0 till i-j<=k
Just to find max element from i till k back
why not do something to get the max in 1 time

Now, we take heap and store the result and index

So heap will always give us max at top and if i-topindex <= k take it
Else pop till you get it
```

{% code title="C++" lineNumbers="true" %}

```cpp
typedef pair<int,int> pii;

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp = nums;
        priority_queue<pii> pq;
        pq.push({dp[0], 0});
        int ans = dp[0];
        for(int index=1; index<n ; index++){
            while(!pq.empty() and index-pq.top().second > k)
                pq.pop();

            dp[index] = max(dp[index], nums[index]+pq.top().first);
            pq.push({dp[index], index});
            ans = max(ans, dp[index]);
        }

        if(ans == 0)
            return *max_element(nums.begin(), nums.end());
        return ans;
    }
};
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/heaps-and-priority-queue/hard/1425.-constrained-subsequence-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.