Constrained Subsequence Sum Python Solution

lcpy gen -n 1425   # by problem number
lcpy gen -s constrained_subsequence_sum   # by problem name

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

from collections import deque


class Solution:
    # Time: O(n)
    # Space: O(k)
    def constrained_subset_sum(self, nums: list[int], k: int) -> int:
        dp = [0] * len(nums)
        window = deque()
        for i, num in enumerate(nums):
            dp[i] = num + (dp[window[0]] if window and dp[window[0]] > 0 else 0)
            while window and dp[window[-1]] <= dp[i]:
                window.pop()
            window.append(i)
            if window[0] <= i - k:
                window.popleft()
        return max(dp)