# 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.

**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 <= 10^5`
* `-10^4 <= nums[i] <= 10^4`

给定数组nums，返回最大的相邻元素所在index的差不超过k的序列和。argmax + seq => DP。遍历并假定当前i元素是序列尾，dp\[i] == 此时最大序列和：argmax(dp\[i - k], dp\[i -k +1], ... dp\[i - 1]) + nums\[i]。找max(dp\[i - k: i - 1])的过程相当于维持一个大小为k的在dp数组上的滑动窗口，且每次找窗口内最大元素=>sliding window maxium，用单调栈：维持deque q，q\[0]是当前窗口内最大值，当dp\[i]进来时，从后面把小于dp\[i]的都抛出；当窗口左边退出来的dp\[i - k] == q\[0]时，从前面抛出q\[0]。

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/heap/1425.-constrained-subsequence-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.