1425. Constrained Subsequence Sum

https://leetcode.com/problems/constrained-subsequence-sum/

from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        #dp[i] means max result you can get if the last one is A[i]
        dp = [0] * n
        #record the max of dp[i-k] to dp[i-1] in decreasing deque
        mmax = deque()
        for i,val in enumerate(nums):
            if len(mmax) > 0:
                dp[i] = val + mmax[0]
            else:
                dp[i] = val
            while len(mmax) > 0 and mmax[-1] < dp[i]:
                mmax.pop()
            if dp[i] > 0:
                mmax.append(dp[i])
            if i >=k and len(mmax) > 0 and dp[i-k] == mmax[0]:
                mmax.popleft()
        return max(dp)