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]。

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)