Constrained Subsequence Sum LeetCode solution in Python

1
# Runtime: 1386 ms (Top 69.5%) | Memory: 30.16 MB (Top 58.7%)
2

3

4
class Solution:
5
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
6
        deque = []
7
        for i, num in enumerate(nums):
8

9
            while (
10
                deque and deque[0] < i - k
11
            ):  # delete that didn't end with a number in A[i-k:i]
12
                deque.pop(0)
13

14
            if deque:  # compute the max sum we can get at index i
15
                nums[i] = nums[deque[0]] + num
16

17
            while deque and nums[deque[-1]] < nums[i]:
18
                # delet all the sequence that smaller than current sum, becaus there will never be
19
                # considers ==> smaller than current sequence, and end before current sequence
20
                deque.pop()
21

22
            if nums[i] > 0:  # if nums[i] < 0, it can't be a useful prefix sum
23
                deque.append(i)
24

25
        return max(nums)