> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/heap/1425.-constrained-subsequence-sum.md).

# 1425. Constrained Subsequence Sum

https\://leetcode.com/problems/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)
```