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