1425. Constrained Subsequence Sum

Description

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

 

Solutions

Solution: Deque

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const constrainedSubsetSum = function (nums, k) {
  const n = nums.length;
  const dp = [...nums];
  const deque = [];
  let result = Number.MIN_SAFE_INTEGER;

  for (let index = 0; index < n; index++) {
    const num = nums[index];

    if (deque.length && index - deque[0] > k) {
      deque.shift();
    }

    if (deque.length) {
      dp[index] = Math.max(dp[index], dp[deque[0]] + num);
    }

    result = Math.max(dp[index], result);

    while (deque.length && dp[deque.at(-1)] < dp[index]) {
      deque.pop();
    }

    deque.push(index);
  }

  return result;
};