Array     C++     Dynamic Programming     Hard     Heap (Priority Queue)     Monotonic Queue     Queue     Sliding Window    

Problem Statement:

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:

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. Then we have the following relation:

 
dp[i] = nums[i] + max(0, dp[i-k], dp[i-k+1], ..., dp[i-1])

Now to get the maximum of a sliding window, we maintain a max heap. The heap has no constraint on size but we enforce the constraint that the heap top is within the current sliding window.

 
class Solution 
{
public:
    int constrainedSubsetSum(vector<int>& nums, int k) 
    {
        priority_queue<pair<int,int>> pq; //(value,index)
        vector<int> dp(nums.size());
        for (int i=0; i<nums.size(); i++)
        {
            while(!pq.empty() && pq.top().second < i-k) pq.pop(); 
            dp[i] = nums[i] + ( i==0 ? 0 : max(0,pq.top().first) );
            pq.push({dp[i],i});
        }
        return *max_element(dp.begin(),dp.end());
    }
};

TC: $O(n \log(n))$, SC: $O(n)$.

Worst case is when the array is sorted in increasing order, hence the heap size is $n$.