1425

1425. Constrained Subsequence Sum (Hard)

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

Companies: Amazon, Akuna Capital

Related Topics:
Array, Dynamic Programming, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue

Similar Questions:

• Maximum Element-Sum of a Complete Subset of Indices (Hard)

Hints:

• Use dynamic programming.
• Let dp[i] be the solution for the prefix of the array that ends at index i, if the element at index i is in the subsequence.
• dp[i] = nums[i] + max(0, dp[i-k], dp[i-k+1], ..., dp[i-1])
• Use a heap with the sliding window technique to optimize the dp.

Solution 1. DP + Monotonic Deque

Let dp[i] be the maximum constrained subsequence sum of A[0..i] ending with A[i]. The answer is max( dp[i] | 0 <= i < N ). Initially dp[i] = A[i].

The transition between dp values are easy to think of:

dp[i] = max(0, max(dp[j] | i-k <= j < i )) + A[i]

Notice this part max(dp[j] | i-k <= j < i ). It's asking for the maximum dp[j] where j is in the window [i-k, i-1]. This is a typical monotonic deque problem.

• We use a monotonic decreasing deque<int> q to store the indices of the possible maximum values within the window i-k <= j <= i-1.
• For a new dp[i] value, we keep popping q.back() if dp[q.back()] <= dp[i].
• Then push i into q.
• Since i-k will go out of window, we pop q.front() if q.front() == i - k.

// OJ: https://leetcode.com/problems/constrained-subsequence-sum/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int constrainedSubsetSum(vector<int>& A, int k) {
        deque<int> q{0};
        vector<int> dp = A;
        for (int i = 1, N = A.size(); i < N; ++i) {
            dp[i] = max(0, dp[q.front()]) + A[i];
            while (q.size() && dp[q.back()] <= dp[i]) q.pop_back();
            q.push_back(i);
            if (q.front() == i - k) q.pop_front();
        }
        return *max_element(begin(dp), end(dp));
    }
};