1425. Constrained Subsequence Sum

Link

Solution

dp[i] = nums[i] + max(dp[i-1], dp[i-2], .... dp[i-k]), dp[k] : the maxsum which ends with nums[k]

How to find the max?

Use Deque to find it.

 public int constrainedSubsetSum(int[] nums, int k) {
        int dp[] = nums.clone(); //dp[i] means the max result in nums[:i]
        int ret = dp[0];
        Deque<Integer> maxBefore = new ArrayDeque<>();
        for(int i = 0; i < nums.length; i++){
            int max = maxBefore.isEmpty()? 0 : maxBefore.peek();
            dp[i] += max; 
            ret = Math.max(ret, dp[i]);
            while(!maxBefore.isEmpty() && maxBefore.peekLast() < dp[i]){
                maxBefore.pollLast();
            }
            if(dp[i] > 0){
                maxBefore.add(dp[i]);
            }
            if( i >= k && !maxBefore.isEmpty() && maxBefore.peek() == dp[i-k]){
                maxBefore.poll();
            }
        }
        return ret;
    }