LeetCode 1425: Constrained Subsequence Sum

Explanation:

To solve this problem, we can use dynamic programming with a deque (double-ended queue) to keep track of the maximum subsequence sum ending at each index. We iterate over the array and at each step, we maintain a deque where the front of the deque contains the maximum sum subsequence within the window size k.

1. Initialize an array dp to store the maximum subsequence sum ending at each index.
2. Initialize a deque deque to maintain the maximum sum subsequence within the window size k.
3. Iterate over the input array nums:
   • Remove elements from the front of the deque that are outside the window (i - deque.peekFirst() > k).
   • Update dp[i] as the maximum between the current element nums[i] and the maximum sum subsequence ending before index i (deque.peekFirst()).
   • Add dp[i] to the deque in a decreasing order.
4. Return the maximum value in the dp array.

import java.util.ArrayDeque;

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (!deque.isEmpty() && i - deque.peekFirst() > k) {
                deque.pollFirst();
            }
            dp[i] = nums[i] + (deque.isEmpty() ? 0 : Math.max(0, dp[deque.peekFirst()]));
            while (!deque.isEmpty() && dp[i] >= dp[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            maxSum = Math.max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
}