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.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

Example 2:

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

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

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

C++

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;
    }
};

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

C++

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;
    }
};

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

C++

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;
    }
};

Approach 4:

C++