1425. Constrained Subsequence Sum

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.

• Time : O(nlogk)
• Space : O(k)

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size(), res = nums.back();
        priority_queue<pair<int,int>> pq;
        pq.push({0,n});
        for(int i = n - 1; i >= 0; i--) {
            while(pq.top().second > i + k) {
                pq.pop();
            }
            int sum = max(pq.top().first + nums[i], nums[i]);
            
            //optimize priority queue operation
            int limit = max(sum,0);
            while(!pq.empty() and pq.top().first <= limit) pq.pop();
            pq.push({limit, i});
            
            res = max(res, sum);
        }
        return res;
    }
};