Problem
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
Solution 1
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var constrainedSubsetSum = function(nums, k) {
var queue = new MaxPriorityQueue();
var max = Number.MIN_SAFE_INTEGER;
for (var i = nums.length - 1; i >= 0; i--) {
while (queue.size() && queue.front().element[1] - i > k) queue.dequeue();
var num = nums[i] + (queue.size() ? queue.front().element[0] : 0);
max = Math.max(max, num);
queue.enqueue([num, i], num);
max = Math.max(max, nums[i]);
queue.enqueue([nums[i], i], nums[i]);
}
return max;
};
Explain:
Priority Queue.
Complexity:
- Time complexity : O(n * log(n)).
- Space complexity : O(n).
Solution 2
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var constrainedSubsetSum = function(nums, k) {
var deque = [];
for (var i = nums.length - 1; i >= 0; i--) {
while (deque.length && deque[deque.length - 1] - i > k) deque.pop();
nums[i] += (deque.length ? nums[deque[deque.length - 1]] : 0);
while (deque.length && nums[deque[0]] <= nums[i]) deque.shift();
if (nums[i] > 0) deque.unshift(i);
}
return Math.max(...nums);
};
Explain:
Monotonic Deque.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).