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

classSolution { public: intconstrainedSubsetSum(vector<int>& nums, int k){ int size = nums.size(); int sum = 0; int max_sum = INT_MIN; int max_num = INT_MIN;

int i; int j = 0;

while (j < size) { if (nums[j] >= 0) { sum += nums[j]; max_sum = max(max_sum, sum); j++; } else { i = j;

sum += maxSum(nums, i, j - 1, k); max_sum = max(max_sum, sum); sum = max(sum, 0); } }

return max_sum < 0 ? max_num : max_sum; }

intmaxSum(vector<int> &nums, int left, int right, int k){ int size = right - left + 1; vector<int> dp(size+1); dp[0] = 0; if (size < k) return0;

for (int len = 1; len <= size; len++) { int max_sum = INT_MIN; for (int i = len - 1; i >= max(len - k, 0); i--) { max_sum = max(max_sum, dp[i] + nums[left + len - 1]); }

dp[len] = max_sum; }

int max_sum = INT_MIN; for (int i = 0; i < k; i++) { max_sum = max(max_sum, dp[size - i]); }

return max_sum; } };

//O(N) classSolution { public: intconstrainedSubsetSum(vector<int>& nums, int k){ int size = nums.size(); deque<int> dq; int max_sum = INT_MIN; for (int i = 0; i < size; i++) { nums[i] += dq.empty() ? 0 : dq.front(); max_sum = max(nums[i], max_sum); while (!dq.empty() && nums[i] > dq.back()) dq.pop_back(); if (nums[i] > 0) dq.push_back(nums[i]); if (i >= k && !dq.empty() && dq.front() == nums[i-k]) dq.pop_front(); } return max_sum; } };