Problem statement

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

Solution

This problem is very similar to 1696. Jump Game VI, but here we can say we can skip some jumps, so we can reuse code for 1696 but instead of nums[i] += nums[deq[0]] we use nums[i] += max(0, nums[deq[0]])

Complexity

Time complexity is O(n), space is O(n) as well.

Code

class Solution:
    def constrainedSubsetSum(self, nums, k):
        deq, n = deque([0]), len(nums)

        for i in range(1, n):
            while deq and deq[0] < i - k: deq.popleft()
            nums[i] += max(0, nums[deq[0]])   
            while deq and nums[i] >= nums[deq[-1]]: deq.pop()
            deq.append(i)
            
        return max(nums)

Remark

There are alternative ways to solve it: using heap with lazy updates or bst, using dp[i] = nums[i] + max(0, dp[i-k], dp[i-k+1], ..., dp[i-1])