# Constrained Subsequence Sum
**Difficulty:** HARD
[External](https://leetcode.com/problems/constrained-subsequence-sum)
Canonical: https://scaleengineer.com/dsa/problems/constrained-subsequence-sum
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Heap (Priority Queue), Queue, Monotonic Queue
**Companies:** [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
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`

# Approaches
## Brute-force Dynamic Programming
This approach uses a straightforward dynamic programming solution. We define `dp[i]` as the maximum sum of a valid subsequence ending at index `i`. To compute `dp[i]`, we must include `nums[i]`. The previous element in the subsequence, say `nums[j]`, must satisfy the condition `j - i <= k`. Therefore, `dp[i]` is `nums[i]` plus the maximum `dp[j]` over the valid range of `j` (i.e., `i - k <= j < i`). If all possible previous subsequence sums are negative, it's better to start a new subsequence from `nums[i]`, so we take the maximum of `0` and the previous maximum sum.
**Time:** O(n * k) - For each element `i` in the input array, we iterate up to `k` previous elements to find the maximum. This results in a nested loop structure. · **Space:** O(n) - We use an auxiliary `dp` array of the same size as the input array.
**Pros:** Simple to understand and implement.; Correctly models the problem's state transitions.
**Cons:** Highly inefficient for large inputs due to the nested loops.; Will result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms for the given constraints.
### Explanation
We create a `dp` array of the same size as `nums`. `dp[i]` will store the maximum constrained subsequence sum that ends with the element `nums[i]`. The core of the algorithm is the recurrence relation:

`dp[i] = nums[i] + max(0, max(dp[j]))` for all `j` such that `i - k <= j < i`.

We can implement this by iterating through the `nums` array from `i = 0` to `n-1`. For each `i`, we have a nested loop that scans the previous `k` elements (from `j = i-1` down to `i-k`) to find the maximum `dp` value in that window. This maximum value is then added to `nums[i]` to compute `dp[i]`. The final answer is the maximum value found in the `dp` array, as the subsequence is not required to end at the last element of the array.

```java
class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            int maxPrev = 0;
            for (int j = Math.max(0, i - k); j < i; j++) {
                maxPrev = Math.max(maxPrev, dp[j]);
            }
            dp[i] = nums[i] + maxPrev;
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}
```
### Algorithm
- Initialize a `dp` array of size `n`, where `n` is the length of `nums`.
- Initialize a variable `maxSum` to `Integer.MIN_VALUE` to keep track of the final result.
- Iterate through the array with an index `i` from `0` to `n-1`:
  - For each `i`, find the maximum value among the previous `k` DP states. Let's call this `maxPrev`. Initialize `maxPrev` to `0`.
  - Iterate with an index `j` from `max(0, i - k)` to `i - 1`.
  - In the inner loop, update `maxPrev = Math.max(maxPrev, dp[j])`.
  - After the inner loop, calculate `dp[i] = nums[i] + maxPrev`.
  - Update the overall maximum: `maxSum = Math.max(maxSum, dp[i])`.
- After the outer loop finishes, return `maxSum`.

## Dynamic Programming with Max Heap
To optimize the brute-force DP, we can speed up the process of finding the maximum value in the sliding window of the last `k` elements. A max heap (or Priority Queue) is a suitable data structure for this task. The heap will store the `dp` values calculated so far, allowing us to retrieve the maximum in `O(log k)` time.
**Time:** O(n log k) - The main loop runs `n` times. Inside the loop, heap operations (insertion and deletion) take `O(log k)` time, as the heap's size is bounded by `k`. · **Space:** O(n) - The `dp` array requires O(n) space, and the heap can store up to `k` elements, so it requires O(k) space. The total is O(n).
**Pros:** Significantly more efficient than the brute-force DP approach.; Passes the time limits for the given constraints on most platforms.
**Cons:** The `log k` factor makes it slower than the optimal linear-time solution.; Requires O(n) extra space for the DP array, which is less space-efficient than the optimal approach.
### Explanation
The DP recurrence relation remains the same: `dp[i] = nums[i] + max(0, max_in_window)`. The optimization comes from how we find `max_in_window`.

We use a max heap that stores pairs of `(value, index)`, ordered by `value`. As we iterate through the array from `i = 0` to `n-1`:
1.  We first check the top of the heap. If its index is outside the current window (i.e., `index < i - k`), we remove it. We repeat this until the top of the heap is a valid predecessor.
2.  Now, the maximum value in the window is at the top of the heap. We retrieve this value to calculate `dp[i]`.
3.  After computing `dp[i]`, we insert the new pair `(dp[i], i)` into the heap.
4.  We continuously track the overall maximum `dp` value to find our final answer.

This reduces the time to find the maximum in the window from O(k) to O(log k), improving the overall time complexity.

```java
import java.util.PriorityQueue;

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        // Max heap storing pairs of [value, index]
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            // Remove elements from heap that are out of the window [i-k, i-1]
            while (!heap.isEmpty() && heap.peek()[1] < i - k) {
                heap.poll();
            }

            int maxPrev = 0;
            if (!heap.isEmpty()) {
                maxPrev = Math.max(0, heap.peek()[0]);
            }

            dp[i] = nums[i] + maxPrev;
            heap.offer(new int[]{dp[i], i});
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}
```
### Algorithm
- Initialize a `dp` array of size `n`.
- Initialize a max heap (Priority Queue in Java) to store pairs of `[value, index]`.
- Initialize `maxSum` to `Integer.MIN_VALUE`.
- Loop `i` from `0` to `n-1`:
  - Remove elements from the top of the heap whose indices are outside the valid window (`index < i - k`).
  - Determine the maximum previous sum, `maxPrev`. If the heap is not empty, `maxPrev` is `heap.peek()[0]`. We take `max(0, maxPrev)`.
  - Calculate `dp[i] = nums[i] + maxPrev`.
  - Add the new pair `[dp[i], i]` to the heap.
  - Update `maxSum = max(maxSum, dp[i])`.
- Return `maxSum`.

## Dynamic Programming with Monotonic Deque
This is the most optimal solution, achieving linear time complexity. It refines the dynamic programming approach by using a monotonic deque to solve the 'Sliding Window Maximum' subproblem efficiently. The deque stores indices of candidates for the maximum value in the current window `[i-k, i-1]`, ensuring that finding this maximum takes amortized O(1) time.
**Time:** O(n) - Each element's index is added to and removed from the deque at most once. All operations inside the loop are amortized O(1). · **Space:** O(k) - The deque will store at most `k+1` indices. By modifying the input array in-place, we avoid the need for a separate O(n) `dp` array.
**Pros:** Optimal time complexity.; Space-efficient, especially with the in-place modification which reduces extra space to O(k).
**Cons:** The logic for maintaining the monotonic deque can be more complex to grasp and implement correctly compared to the heap-based solution.
### Explanation
We maintain a deque of indices `j` such that the corresponding DP values (`dp[j]`) are in decreasing order. This means the index corresponding to the maximum value in the current window is always at the front of the deque.

For each index `i` from `0` to `n-1`, we perform the following steps:
1.  **Find Window Max:** The maximum `dp` value in the window `[i-k, i-1]` is simply `dp[deque.peekFirst()]` (if the deque is not empty).
2.  **Calculate `dp[i]`:** We calculate `dp[i]` using the value from step 1. To save space, we can store the `dp` values in the input `nums` array itself. So, `nums[i]` becomes `nums[i] + max(0, nums[deque.peekFirst()])`.
3.  **Maintain Monotonicity:** Before adding `i` to the deque, we pop indices from the back of the deque as long as their corresponding `dp` values are less than or equal to `dp[i]`. This ensures the decreasing order property is preserved.
4.  **Update Window:** We remove the index from the front of the deque if it falls out of the `k`-sized window (i.e., `deque.peekFirst() <= i - k`).

By doing this, each index is pushed and popped from the deque at most once, leading to an overall linear time complexity.

```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        // Deque will store indices j such that nums[j] (which represents dp[j])
        // are in decreasing order.
        Deque<Integer> deque = new ArrayDeque<>();
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            // Get previous max from the window
            int prevMax = 0;
            if (!deque.isEmpty()) {
                prevMax = nums[deque.peekFirst()];
            }

            // Calculate dp[i] (in-place in nums array)
            if (prevMax > 0) {
                nums[i] += prevMax;
            }
            
            maxSum = Math.max(maxSum, nums[i]);

            // Maintain monotonic property of the deque
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);

            // Maintain window size
            if (i - deque.peekFirst() >= k) {
                deque.pollFirst();
            }
        }
        return maxSum;
    }
}
```
### Algorithm
- Initialize a deque (double-ended queue) to store indices.
- Initialize `maxSum` to `Integer.MIN_VALUE`.
- Iterate `i` from `0` to `n-1`:
  - If the deque is not empty, the maximum value in the current window is at the front of the deque. Let `prevMax = nums[deque.peekFirst()]`.
  - Calculate the current DP value by updating `nums[i]` in-place: if `prevMax > 0`, `nums[i] += prevMax`.
  - Update the overall `maxSum = Math.max(maxSum, nums[i])`.
  - To maintain the deque's monotonic property, remove indices from the end of the deque whose `nums` values are less than or equal to the current `nums[i]`.
  - Add the current index `i` to the end of the deque.
  - Remove the index from the front of the deque if it's now outside the window of size `k` (i.e., `i - deque.peekFirst() >= k`).
- Return `maxSum`.

# Solutions
### Java

```java
class Solution {
public
  int constrainedSubsetSum(int[] nums, int k) {
    int n = nums.length;
    int[] dp = new int[n];
    int ans = Integer.MIN_VALUE;
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      if (!q.isEmpty() && i - q.peek() > k) {
        q.poll();
      }
      dp[i] = Math.max(0, q.isEmpty() ? 0 : dp[q.peek()]) + nums[i];
      while (!q.isEmpty() && dp[q.peekLast()] <= dp[i]) {
        q.pollLast();
      }
      q.offer(i);
      ans = Math.max(ans, dp[i]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int constrainedSubsetSum(vector<int> &nums, int k) {
    int n = nums.size();
    vector<int> dp(n);
    int ans = INT_MIN;
    deque<int> q;
    for (int i = 0; i < n; ++i) {
      if (!q.empty() && i - q.front() > k)
        q.pop_front();
      dp[i] = max(0, q.empty() ? 0 : dp[q.front()]) + nums[i];
      ans = max(ans, dp[i]);
      while (!q.empty() && dp[q.back()] <= dp[i])
        q.pop_back();
      q.push_back(i);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int: n = len(nums) dp = [0] * n ans = - inf q = deque() for i, v in enumerate(nums): if q and i - q[0] > k: q . popleft() dp[i] = max(0, 0 if not q else dp[q[0]]) + v while q and dp[q[- 1]] <= dp[i]: q . pop() q . append(i) ans = max(ans, dp[i]) return ans

```