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

Difficulty: interview

Starter code:

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        

Solutions:
from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums, k):
        N, queue = len(nums), deque()
        dp = [val for val in nums]
        for i, val in enumerate(nums):
            if queue and (i - queue[0] > k):
                queue.popleft()
            if queue and dp[queue[0]] > 0:
                dp[i] += dp[queue[0]]
            while queue and dp[i] >= dp[queue[-1]]:
                queue.pop()
            queue.append(i)
        return max(dp)

from collections import deque

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp = nums.copy()
        ans = dp[0]

        monoq = deque()
        qsize = 0
        
        for i, num in enumerate(nums):
            if i > 0:   
                dp[i] = max(dp[i], num + monoq[0][0])
            ans = max(ans, dp[i])
            
            pops = 1
            while monoq and dp[i] > monoq[-1][0]:
                _, freq = monoq.pop()
                pops += freq
                qsize -= freq
            monoq.append([dp[i], pops])
            qsize += pops

            while qsize > k:
                extra = qsize - k
                if monoq[0][1] > extra:
                    monoq[0][1] -= extra
                    qsize = k
                else:
                    _, v = monoq.popleft()
                    qsize -= v
            
        return ans


from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp = []
        dp.append(nums[0])
        deq = deque()
        deq.append(0)
        for i in range(1, len(nums)):
            while len(deq) and (i - deq[0]) > k:
                deq.popleft()
            cur_max = dp[deq[0]] if len(deq) and dp[deq[0]] > 0 else 0
            dp.append(cur_max + nums[i])
            while len(deq) and dp[deq[-1]] < dp[i]:
                deq.pop()
            deq.append(i)
        return max(dp)

from heapq import heappop
from heapq import heappush

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        # -val, val, idx
        heap = []
        ans = -10001
        for i, num in enumerate(nums):
            while len(heap) > 0:
                _, val, idx = heap[0]
                if idx < i - k: # out of constraint
                    heappop(heap)
                else:
                    new_val = max(num, val + num)
                    ans = max(ans, new_val)
                    heappush(heap, (-new_val, new_val, i))
                    break
                    
            if len(heap) == 0:  # no valid previous item
                ans = max(ans, num)
                heappush(heap, (-num, num, i))
        return ans


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n=len(nums)
        dp=[-sys.maxsize]*n
        dq=[]
        dp[n-1]=nums[n-1]
        res=dp[n-1]
        for i in range(n-2,-1,-1):
            while(len(dq)!=0 and dp[i+1]>dp[dq[-1]]):
                dq.pop()
            while(len(dq)!=0 and dq[0]>i+k):
                dq.pop(0)
            dq.append(i+1)
            dp[i]=max(dp[i],nums[i],nums[i]+dp[dq[0]])
            res=max(res,dp[i])
            
            
        return res


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        withAdding = [0 for _ in range(len(nums))]
        notAdding = [-1 for _ in range(len(nums))]
        
        validMax = [nums[0]]
        maxValue = nums[0]
        withAdding[0] = nums[0]
        
        for i in range(1, len(nums)):
            if maxValue < 0 and nums[i] > maxValue:
                withAdding[i] = nums[i]
            else:
                withAdding[i] = maxValue + nums[i]
            
            validMax.append(withAdding[i])
            maxValue = max(withAdding[i], maxValue)
            if len(validMax) > k and validMax.pop(0) == maxValue:
                maxValue = max(validMax)
                
            notAdding[i] = max(notAdding[i - 1], withAdding[i - 1])
            
            
        return max(max(notAdding), max(withAdding))


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        memo=[nums[0]]
        if not nums:
            return 0
        m=nums[0]
        for i in range(1,k):
            memo.append(nums[i]+max(0,m))
            if memo[-1]>m:
                m=memo[-1]
        import copy
        window=copy.deepcopy(memo)
        #m=max(window)
        for i in range(k,len(nums)):
            #print(m,memo,window)
            memo.append(nums[i]+max(0,m))
            window.append(memo[-1])
            p=window.pop(0)
            if memo[-1]>m:
                m=memo[-1]
            elif p==m:
                m=max(window)
        return max(memo)

from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums, k):
        N, queue = len(nums), deque()
        dp = [0] * N
        for i, val in enumerate(nums):
            if queue and (i - queue[0] > k):
            #if i > k and (queue[0] == i - k - 1):
                queue.popleft()
            #dp[i] = (val + max(dp[queue[0]], 0)) if queue else val
            if queue and dp[queue[0]] > 0:
                dp[i] = val + dp[queue[0]]
            else:
                dp[i] = val
            while queue and dp[i] >= dp[queue[-1]]:
                queue.pop()
            queue.append(i)
        return max(dp)
        
from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums, k):
        if not nums or not k: return 0
        if max(nums) <= 0: return max(nums)
        if min(nums) >= 0: return sum(nums)
        queue, N = deque(), len(nums)
        for i in range(N):
            #if queue and (i - queue[0] > k):
            while queue and queue[0] < i - k:
                queue.popleft()
            # compute the max sum we can get at index i
            if queue:
                nums[i] += nums[queue[0]]
            # delet all the sequence that smaller than current sum, becaus there will never be
            # considers ==> smaller than current sequence, and end before current sequence
            while queue and nums[queue[-1]] < nums[i]:
                queue.pop()
            # if nums[i] < 0, it can't be a useful prefix sum
            if nums[i] > 0:
                queue.append(i)
        return max(nums)

from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums, k):
        if max(nums) <= 0: return max(nums)   # optimization
        if min(nums) >= 0: return sum(nums)   # optimization
    
        N, queue = len(nums), deque()
        dp = [val for val in nums]
        for i, val in enumerate(nums):
            if queue and (i - queue[0] > k):
                queue.popleft()
            if queue and dp[queue[0]] > 0:
                dp[i] += dp[queue[0]]
            while queue and dp[i] >= dp[queue[-1]]:
                queue.pop()
            queue.append(i)
        return max(dp)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp=[nums[0]]
        decrease=collections.deque([0])
        for i,num in enumerate(nums[1:],1):
            if decrease and i-decrease[0]>k:
                decrease.popleft()
            val=max(num,dp[decrease[0]]+num)
            dp.append(val)
            while decrease and dp[decrease[-1]]<=val:
                decrease.pop()
            decrease.append(i)
            
        return max(dp)

from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums, k):
        if max(nums) <= 0: return max(nums)   # optimization
        if min(nums) >= 0: return sum(nums)   # optimization
    
        N, queue = len(nums), deque()
        dp = [val for val in nums]
        for i, val in enumerate(nums):
            if queue and (i - queue[0] > k):
                queue.popleft()
            if queue and dp[queue[0]] > 0:
                dp[i] += dp[queue[0]]
            while queue and dp[i] >= dp[queue[-1]]:
                queue.pop()
            queue.append(i)
        return dp[queue[0]]

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        _max = collections.deque()
        res = max(nums)
        
        for i in range(n):
            if len(_max) and _max[0][0] > 0:
                val = nums[i] + _max[0][0]
            else:
                val = nums[i]
            while len(_max) and _max[-1][0] < val: _max.pop()
            _max.append((val, i))
            res = max(val, res)
        
            if _max[0][1] <= i-k:
                _max.popleft()
    
        return res


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        maxNum = nums[0]
        maxSum = nums[0]
        maxNegSum = 0
        curNegWindowSum = 0
        curWindowSum = 0
        rightIndex = 0 
        leftIndex = 0
        midIndex = 0
        negativeStreak = False
        
        while rightIndex < len(nums):
            if maxNum < nums[rightIndex]:
                maxNum = nums[rightIndex]
                
            if nums[rightIndex] >= 0 and not negativeStreak: 
                curWindowSum += nums[rightIndex]
                maxSum = max(maxSum, curWindowSum)
            elif nums[rightIndex] < 0 and not negativeStreak:
                negativeStreak = True
                midIndex = rightIndex
                if k > 1:
                    curNegWindowSum = nums[rightIndex]
                    maxNegSum = curNegWindowSum
                curWindowSum += nums[rightIndex]
            elif nums[rightIndex] < 0 and negativeStreak:
                if rightIndex - midIndex < k - 1:
                    curNegWindowSum += nums[rightIndex]
                    maxNegSum = curNegWindowSum
                else:
                    if k > 1:
                        curNegWindowSum -= nums[midIndex]
                        curNegWindowSum += nums[rightIndex]
                    maxNegSum = min(maxNegSum, curNegWindowSum)
                    midIndex += 1
                curWindowSum += nums[rightIndex]
            elif nums[rightIndex] >= 0 and negativeStreak:
                curWindowSum -= maxNegSum
                if curWindowSum <= 0:
                    midIndex = rightIndex
                    leftIndex = rightIndex
                    curWindowSum = nums[rightIndex]
                else:
                    curWindowSum += nums[rightIndex]
                maxSum = max(maxSum, curWindowSum)
                maxNegSum = 0
                curNegWindowSum = 0
                negativeStreak = False
            
            rightIndex += 1
        return max(maxSum, maxNum)
            


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp = [nums[0]]
        decrease = collections.deque([0])
        for i, x in enumerate(nums[1:], 1):
            if decrease[0] == i-k-1:
                decrease.popleft()
            tmp = max(x, dp[decrease[0]] + x)
            dp += [tmp]
            while decrease and dp[decrease[-1]] <= tmp:
                decrease.pop()
            decrease += [i]            
        return max(dp)  

class Solution:
    def constrainedSubsetSum(self, A: List[int], k: int) -> int:
        deque = collections.deque()
        for i in range(len(A)):
            A[i] += deque[0] if deque else 0
            while len(deque) and A[i] > deque[-1]:
                deque.pop()
            if A[i] > 0:
                deque.append(A[i])
            if i >= k and deque and deque[0] == A[i-k]:
                deque.popleft()
        
        return max(A)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        q_max, ans = deque([(nums[0],0)]), nums[0]
        for i in range(1,len(nums)):
            nums[i] += max(q_max[0][0],0)
            if q_max[0][1] <= i-k:
                q_max.popleft()
            while q_max and nums[i] > q_max[-1][0]:
                q_max.pop()
            q_max.append((nums[i],i))
            ans = max(ans, nums[i])
        return ans


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dq=collections.deque()
        
        m=-sys.maxsize
        for i,n in enumerate(nums):
            fi = n
            
            if dq:
                fi += max(dq[0][1], 0)
            while dq and fi>=dq[-1][1]:
                dq.pop()
                
            dq.append([i,fi])
            
            if i-dq[0][0]==k:
                dq.popleft()
                
            if fi>m:
                m=fi
                
        return m
            
            
        
        


class Solution:
    def constrainedSubsetSum(self, nums, k):
        n = len(nums)
        dp = [0] * n
        deq = deque([0])
        for i in range(n):
            if deq and deq[0] < i - k:
                deq.popleft()
            while deq and nums[i] + dp[deq[0]] > dp[deq[-1]]:
                a = deq.pop()
            dp[i] = max(nums[i],nums[i] + dp[deq[0]] if deq else nums[i] + dp[a])
            deq.append(i)

        return max(dp)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        q = deque([0])
        ans = nums[0]
        for i in range(1, len(nums)):
            nums[i] += max(nums[q[0]], 0)
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
            if i - q[0] == k:
                q.popleft()
            
            ans = max(ans, nums[i])
                
        return ans

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp, q = [nums[0]], deque()
        q.append((0,nums[0]))
        res = nums[0]
        for i in range(1, len(nums)):
            while q and i - q[0][0] >k:
                q.popleft()
            cur = nums[i]
            if q:
                cur +=max(q[0][1],0)
            while q and q[-1][1] < cur:
                q.pop()
            q.append((i,cur))
            dp.append(cur)
            res = max(res,cur)
        return res
            
        



from collections import deque
class Solution:
    def constrainedSubsetSum(self, A: List[int], k: int) -> int:
        d = deque()
        for i in range(len(A)):
            A[i] += d[0] if d else 0
            while d and d[-1] < A[i]:
                d.pop()
            if A[i] > 0:
                d.append(A[i])
            if i >= k and d and d[0] == A[i - k]:
                d.popleft()
        return max(A)

from collections import deque
'''
We need to figure out basically for k numbers remaining what is the largest sum, assuming that the first of those is selected.
'''
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        numLength = len(nums)
        maxSums = defaultdict(int)
        maxSum = nums[0]##as that is definitely a lower bound on the maxSum, as that is obviously a possible sum. Be careful when you initialize mins and maxs
        maxQueue = deque([0])##this will be used to compute the list of values of the maxSum for the previousk indices.
        for i in range(numLength-1,-1,-1):
            ithMax = max(nums[i],maxQueue[0]+nums[i])##be careful of index name.
            maxSums[i] = ithMax
            ##print(\"Max Queue before popping: \",maxQueue)
            if len(maxQueue) == k:##be careful of variables
                if maxSums[i+k] == maxQueue[0]:
                    maxQueue.popleft()##this is needed to ensure that we don't have values that have expired.
            while maxQueue and ithMax > maxQueue[-1]:##be sure of spelling and using right variables
                maxQueue.pop()
            maxQueue.append(ithMax)
            ##print(\"Max Queue after popping: \",maxQueue)
            maxSum = max(ithMax,maxSum)
        return maxSum

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:

        dp = collections.deque([(nums[0], 0)])
        ans = nums[0]
        
        for i in range(1, len(nums)):
    
            new = nums[i] + max(0,dp[0][0])
            
            while dp and dp[0][1] <= i-k:
                dp.popleft()            
            
            while dp and new >= dp[-1][0]:
                dp.pop()
            
            dp.append((new, i))
            
            ans = max(ans, new)
    
        return ans


from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums, k):
        if max(nums) <= 0: return max(nums)
        if min(nums) >= 0: return sum(nums)

        queue, N = deque(), len(nums)
        for i in range(N):
            while queue and queue[0] < i - k:
                queue.popleft()
            if queue:
                nums[i] += nums[queue[0]]
            while queue and nums[queue[-1]] < nums[i]:
                queue.pop()
            if nums[i] > 0:
                queue.append(i)
        return max(nums)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n= len(nums)
        dp = [0]*n
        q = deque()
        ans = float('-inf')
        for i in range(n):
            if i>k and q[0]==i-k-1:
                q.popleft()
            dp[i]= (0 if len(q)==0 else max(dp[q[0]],0)) + nums[i]
            while len(q)>0 and dp[i]>=dp[q[-1]]:
                q.pop()
            q.append(i)
            ans = max(ans, dp[i])
        return ans

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        # dp[i] = nums[i] + max(dp[j] j - i <= k)
        # max(dp)
        n = len(nums)
        from collections import deque
        q = deque()
        q.append((nums[-1], n-1))
        ans = nums[-1]
        for i in reversed(list(range(n-1))):
            while q and q[0][1] - i > k:
                q.popleft()
            dp = nums[i]
            if q:
                dp = max(dp, nums[i] + q[0][0])
            ans = max(dp, ans)
            while q and q[-1][0] <= dp:
                q.pop()
            q.append((dp, i))
        return ans
        


from collections import deque

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        
        n = len(nums)
        queue = deque()
        res = float('-inf')
        
        for i in range(n):
            
            if queue and i - queue[0][1] > k:
                queue.popleft()
            
            cur = nums[i] + max(0, (queue[0][0] if queue else 0))
            res = max(res, cur)
            
            while queue and queue[-1][0] <= cur:
                queue.pop()
            queue.append((cur, i))
                
        return res


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        q = []
        res = float('-inf')
        for i in range(len(nums)):
            while q and i-q[0][0] > k:
                q.pop(0)
            temp = nums[i]
            if q and q[0][1] > 0:
                temp += q[0][1]
            res = max(res, temp)
            while q and q[-1][1] <= temp:
                q.pop()
            q.append((i, temp))
        return res

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        N = len(nums)
        dp = [-math.inf] * N
        
        q = deque()   #. Val, Index
        for i in range(N):
            dp[i] = max(dp[i], nums[i] + (q[0][0] if q else 0), nums[i] )
            
            while q and dp[i] > q[-1][0]:
                q.pop()
            while q and i - q[0][1] >= k:
                q.popleft()
            q.append((dp[i], i))
        
        # print(dp)
        return max(dp)


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        deq = deque()
        for index, val in enumerate(nums):
            nums[index] += deq[0] if deq else 0
            while deq and nums[index]> deq[-1]:
                deq.pop()
            if nums[index]>0:
                deq.append(nums[index])
            if index>=k and deq and deq[0] == nums[index-k]:
                deq.popleft()
        return max(nums)


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] *n
        dp[0] = nums[0]
        heap = []
        heappush(heap, (- nums[0], 0))
        for i in range(1, n):
            while heap[0][1] < i - k:
                heappop(heap)
            cur = heap[0][0]
            
            dp[i] = nums[i] + max(- cur, 0)
            heappush(heap, (- dp[i], i))
        #print(dp)
        return max(dp)
                    


class Solution:
        def constrainedSubsetSum(self, A, k):
            deque = collections.deque()
            for i in range(len(A)):
                A[i] += deque[0] if deque else 0
                while len(deque) and deque[-1] < A[i]:
                    deque.pop()
                if A[i] > 0:
                    deque.append(A[i])
                if i >= k and deque and deque[0] == A[i - k]:
                    deque.popleft()
            return max(A)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [-(math.inf) for i in range(n)]
        dp[0] = nums[0]
        ans = [nums[0]]
        queue = [0]
        for i in range(1,n):
            dp[i] = max(dp[i], nums[i], nums[i]+ans[i-1])
            if len(queue) == 0:
                queue.append(i)
            else:
                while len(queue) > 0 and  ((dp[i] > dp[queue[-1]]) or (i - queue[0]) >= k):
                    if dp[i] > dp[queue[-1]]:
                        queue.pop(-1)
                    else:
                        queue.pop(0)
                queue.append(i)
            ans.append(dp[queue[0]])
        # print(ans)
        # print(dp)
        return (max(dp))


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        stack = deque()
        
        for i in range(len(nums)):
            nums[i] += stack[0] if stack else 0
            while stack and stack[-1] < nums[i]:
                stack.pop()
            if i >= k and stack and stack[0] == nums[i-k]:
                stack.popleft()
            if nums[i] > 0:
                stack.append(nums[i])
        return max(nums)
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        q = deque()
        for i in range(len(nums)):
            nums[i] += q[0] if q else 0
            while q and nums[i] > q[-1]:
                q.pop()
            if nums[i] > 0:
                q.append(nums[i])
            if i >= k and q and q[0] == nums[i-k]:
                q.popleft()
        return max(nums)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        #用来保留k步内的累加最大值
        deque = collections.deque()
        for i in range(len(nums)):
            if deque:
               nums[i] += deque[0]
            
            while deque and nums[i] > deque[-1]:
                deque.pop()
            
            if nums[i] > 0:
                deque.append(nums[i])
            #去除超过k步的最大值，为下一步要加的的最大值做准备
            if i >= k and deque and deque[0] == nums[i - k]:
                deque.popleft()
            
        return max(nums)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        res = -sys.maxsize
        
        n = len(nums)
        dp = [0]*(n+1)
        dq = collections.deque()
        
        for i in range(n):
            if not dq:
                dp[i+1] = nums[i]
            else:
                dp[i+1] = max(nums[i], dq[0] + nums[i])
            dq.append(dp[i+1])
            while len(dq) > k:
                dq.popleft()
            while len(dq) > 1 and dq[0] <= dq[-1]:
                dq.popleft()
            
            res = max(res, dp[i+1])
        
        return res

from typing import List
import collections


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        
        maxx = list(nums)
        deque = collections.deque()
        for i in range(len(nums)):
            if deque:
                maxx[i] += deque[0]
            while deque and maxx[i] > deque[-1]:
                deque.pop()
            if maxx[i] > 0:
                deque.append(maxx[i])
            if i >= k and deque and deque[0] == maxx[i - k]:
                deque.popleft()
        return max(maxx)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        rec = -nums[0]
        heap = [(-nums[0], 0)]
        for j, n in enumerate(nums[1:]):
            while j+1-heap[0][1] > k:
                heapq.heappop(heap)
            cand = -n + heap[0][0] if heap[0][0] <= 0 else -n
            rec = min(rec, cand)
            heapq.heappush(heap, (cand, j+1))
        return -rec

class MonoQ:
    def __init__(self,k):
        self.k = k
        self.m = []
        
    def add(self,a,solution):
        while len(self.m) > 0:
            if solution[a] > solution[self.m[-1]]:
                self.m.pop()
            else:
                break
        self.m.append(a)
    
    def grab(self, a, solution, nums):
        if len(self.m) > 0:
            if self.m[0] > a+self.k:
                self.m = self.m[1:]
            return max(nums[a],nums[a]+solution[self.m[0]])
        else:
            return nums[a]
        
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        solution = [0]*n
        m = MonoQ(k)
    
        for i in range(n-1,-1,-1):
            solution[i] = m.grab(i,solution,nums)
            m.add(i,solution)

        return max(solution)
    
    


import heapq

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        heap = []
        n = len(nums)
        dp = [None] * n 
        for i in range(n):
            best = None
            while len(heap) > 0:
                val, idx = heap[0]
                val *= (-1)

                if i - idx <= k:
                    best = val
                    break
                    
                heapq.heappop(heap)

            dp[i] = nums[i]
            if best is not None and dp[i] < best + nums[i]:
                dp[i] = best + nums[i]
                
            #print(dp)

            heapq.heappush(heap, (-dp[i], i))
        return max(dp)

from heapq import heappush, heappop

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        # [-max_sum, idx]
        
        res = -float('inf')
        queue = []
        for i, x in enumerate(nums):
            while queue and queue[0][1] < i - k:
                heappop(queue)
                
            if queue:
                y = x - queue[0][0]
            else:
                y = x
            
            res = max(res, y)
            if y > 0:
                heappush(queue, [-y, i])
                
        return res

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        max_queue = collections.deque([0,])
        max_sum = nums[0]
        for i in range(1, len(nums)):   
            while max(0,i-k)>max_queue[0]:
                max_queue.popleft()
            nums[i] += max(0, nums[max_queue[0]])
            max_sum = max(max_sum, nums[i])
            while max_queue and nums[max_queue[-1]]<nums[i]:
                max_queue.pop()
            max_queue.append(i)

        return max_sum


from heapq import heappush, heappop

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        res = -float('inf')
        queue = list()
        for i, x in enumerate(nums):
            while queue and queue[0][1] < i - k:
                heappop(queue)
            if queue:
                val, idx = queue[0]
                if val < 0:
                    x -= val
            heappush(queue, [-x, i])
            res = max(res, x)
        return res


import collections

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        # Like jump game 
        # At nums[i], add the max of [num[i-k], ... num[i-1], 0]
        # this can be done by deque with max k
        
        sol = -float('inf')
        n = len(nums)
        maxque = collections.deque([(-1,0)])
        for i in range(n):
            max_i = max(maxque[0][1],0) + nums[i]
            sol = max(sol, max_i)
            while maxque:
                if maxque[-1][1] < max_i:
                    maxque.pop()
                else:
                    break
            maxque.append((i,max_i))
            if maxque[0][0] <= i-k:
                maxque.popleft()
        return sol
        
        


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp = [n for n in nums]
        heap = [(-nums[0], 0)]
        for j in range(1, len(nums)):
            while heap[0][1] < j - k:
                heapq.heappop(heap)
            dp[j] = max(dp[j], -heap[0][0] + nums[j])
            heapq.heappush(heap, (-dp[j], j))
        return max(dp)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n=len(nums)
        dp=[-sys.maxsize]*n
        dq=collections.deque([])
        dp[n-1]=nums[n-1]
        res=dp[n-1]
        for i in range(n-2,-1,-1):
            while(len(dq)!=0 and dp[i+1]>dp[dq[-1]]):
                dq.pop()
            while(len(dq)!=0 and dq[0]>i+k):
                dq.popleft()
            dq.append(i+1)
            dp[i]=max(dp[i],nums[i],nums[i]+dp[dq[0]])
            res=max(res,dp[i])
            
            
        return res


class Solution:
    def constrainedSubsetSum(self, A: List[int], k: int) -> int:
        d = collections.deque()
        for i in range(len(A)):
            A[i] += d[0] if d else 0
            while d and A[i] > d[-1]:
                d.pop()
            if A[i] > 0:
                d.append(A[i])
            if i >= k and d and d[0] == A[i-k]:
                d.popleft()
        return max(A)


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        pq = [(-nums[0], 0)]
        res = nums[0]
        for i in range(1, len(nums)):
            rm = i - k - 1
            while pq[0][1] <= rm:
                heapq.heappop(pq)
            cur = max(-pq[0][0], 0) + nums[i]
            res = max(res, cur)
            heapq.heappush(pq, (-cur, i))
        return res

import heapq

class Solution:
  def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
    n = len(nums)
    # dp: walk backward, optimized dp process
    ans = nums.copy()
    q = []
    for i in range(n - 1, -1, -1):
      # armortized O(1)
      while q and q[0][1] - i > k:
        heapq.heappop(q)
      if q:
        ans[i] += max(0, -q[0][0])
      heapq.heappush(q, (-ans[i], i))
    return max(ans)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp=[-sys.maxsize]*len(nums)
        ans=nums[0]
        dp[0]=nums[0]
        heap=[(-nums[0],0)]
        heapq.heapify(heap)
        for i in range(1,len(nums)):
            bound=i-k
            while heap[0][1]<bound:
                heapq.heappop(heap)
            dp[i]=max(dp[i],nums[i],-heap[0][0]+nums[i])
            ans=max(ans,dp[i])
            heapq.heappush(heap,(-dp[i],i))
        return ans

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        q = [(-nums[0], 0)]
        res = nums[0]
        dp = [0] * n
        
        for i in range(1, n):
            while q and i - q[0][1] > k:
                heapq.heappop(q)
                
            t = max(nums[i] - q[0][0], nums[i])
            res = max(res, t)
            heapq.heappush(q, (-t, i))
            
        return res

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        q = collections.deque()
        for i in range(len(nums)):
            nums[i] += q[0] if q else 0
            
            while q and nums[i] > q[-1]:
                q.pop()
                
            if nums[i] > 0:
                q.append(nums[i])
                
            if i >= k and q and q[0] == nums[i-k]:
                q.popleft()
                
        return max(nums)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        q = collections.deque()
        result = nums[0]
        for i in range(n):
            while q and q[0][1] < i - k:
                q.popleft()
            a = q[0][0] if q else 0
            m = nums[i] + (a if a > 0 else 0)
            while q and m >= q[-1][0]:
                q.pop()
            q.append((m, i))
            result = max(result, m)
        return result

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        heap = [(-nums[0], 0)]
        ret = nums[0]

        for i in range(1, len(nums)):
            remove = i - k - 1
            while remove >= heap[0][1]:
                heapq.heappop(heap)

            cur = max(0, -heap[0][0]) + nums[i]
            ret = max(ret, cur)
            heapq.heappush(heap, (-cur, i))
        return ret


from collections import deque

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp = nums.copy()
        ans = dp[0]

        monoq = deque()
        qsize = 0
        
        for i, num in enumerate(nums):
            if i > 0:   
                dp[i] = max(dp[i], num + monoq[0][0])
            ans = max(ans, dp[i])
            
            pops = 1
            while monoq and dp[i] > monoq[-1][0]:
                _, freq = monoq.pop()
                pops += freq
                qsize -= freq
            monoq.append([dp[i], pops])
            qsize += pops

            while qsize > k:
                extra = qsize - k
                if monoq[0][1] > extra:
                    monoq[0][1] -= extra
                    qsize = k
                else:
                    _, v = monoq.popleft()
                    qsize -= v
            
        return ans


from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums, k):
        N, queue = len(nums), deque()
        dp = [0] * N
        for i, val in enumerate(nums):
            if queue and (i - queue[0] > k):
            #if i > k and (queue[0] == i - k - 1):
                queue.popleft()
            #dp[i] = (val + max(dp[queue[0]], 0)) if queue else val
            if queue and dp[queue[0]] > 0:
                dp[i] = val + dp[queue[0]]
            else:
                dp[i] = val
            while queue and dp[i] >= dp[queue[-1]]:
                queue.pop()
            queue.append(i)
        return max(dp)
        
from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums, k):
        if not nums or not k: return 0
        if max(nums) <= 0: return max(nums)
        if min(nums) >= 0: return sum(nums)
        queue, N = deque(), len(nums)
        for i in range(N):
            #if queue and (i - queue[0] > k):
            while queue and queue[0] < i - k:
                queue.popleft()
            # compute the max sum we can get at index i
            if queue:
                nums[i] += nums[queue[0]]
            # delet all the sequence that smaller than current sum, becaus there will never be
            # considers ==> smaller than current sequence, and end before current sequence
            while queue and nums[queue[-1]] < nums[i]:
                queue.pop()
            # if nums[i] < 0, it can't be a useful prefix sum
            if nums[i] > 0:
                queue.append(i)
        return max(nums)
    
    
    
from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums, k):
        N, queue = len(nums), deque()
        dp = [val for val in nums]
        for i, val in enumerate(nums):
            if queue and (i - queue[0] > k):
                queue.popleft()
            if queue and dp[queue[0]] > 0:
                dp[i] += dp[queue[0]]
            while queue and dp[i] >= dp[queue[-1]]:
                queue.pop()
            queue.append(i)
        return max(dp)


from collections import deque


class Solution:
    def constrainedSubsetSum(self, A: List[int], k: int) -> int:
        Q = deque([(0, A[0])])  # decreasing
        running_max = A[0]
        for i in range(1, len(A)):
            if Q[0][0] < i - k:
                Q.popleft()
            maxsum_of_subseq_ends_at_i = A[i] + max(Q[0][1], 0)
            running_max = max(maxsum_of_subseq_ends_at_i, running_max)
            while Q and Q[-1][1] <= maxsum_of_subseq_ends_at_i:
                Q.pop()
            Q.append((i, maxsum_of_subseq_ends_at_i))

        return running_max


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [-sys.maxsize] * n
        dp[0] = nums[0]
        maxDeque = deque()
        
        ans = -sys.maxsize
        for j in range(n):
            while len(maxDeque) > 0 and j - maxDeque[0] > k:
                maxDeque.popleft()
            preMax = dp[maxDeque[0]] if len(maxDeque) > 0 else 0
            dp[j] = max(preMax + nums[j], nums[j])
            ans = max(dp[j], ans)
            while len(maxDeque) > 0 and dp[maxDeque[-1]] < dp[j]:
                maxDeque.pop()
            maxDeque.append(j)
        
        return ans

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp, res = collections.deque(), -float('inf')
        for i, n in enumerate(nums):
            if dp and dp[0][0] < i - k:
                dp.popleft()
            cur = n + (0 if not dp else dp[0][1])
            res = max(res, cur)
            if cur > 0:
                while dp and dp[-1][1] <= cur:
                    dp.pop()
                dp.append((i, cur))
            # print('dp', dp)
        return res
        


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n=len(nums)
        dp=[0]*n
        remove=collections.defaultdict(int)
        h=[]
        def get_b():
            if not h:
                return 0
            b=heapq.heappop(h)
            while remove[b]>0:
                remove[b]-=1
                b=heapq.heappop(h)
            heapq.heappush(h,b)
            return -b
        for i,d in enumerate(nums):
            if i>k:
                remove[-dp[i-k-1]]+=1
            dp[i]=max(get_b(),0)+d
            heapq.heappush(h,-dp[i])
        return max(dp)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        q = collections.deque()
        result = nums[0]
        for i in range(n):
            while q and q[0][1] < i - k:
                q.popleft()
            a = q[0][0] if q else 0
            m = nums[i] + (a if a > 0 else 0)
            if m > 0:
                while q and m >= q[-1][0]:
                    q.pop()
                q.append((m, i))
            result = max(result, m)
        return result

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp = [0 - sys.maxsize for i in range(len(nums))]
        heap = []
        
        dp[0] = nums[0]
        heapq.heappush(heap, (0-nums[0], 0))
        for i in range(1,len(nums)):
            while len(heap) and heap[0][1] < i - k:
                heapq.heappop(heap)
            dp[i] = max(dp[i], nums[i] + max(0, 0 - heap[0][0] if len(heap) else 0))
            heapq.heappush(heap, (0 - dp[i], i))
        return max(dp)
            
            
        
        
        


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        heap = [(-nums[0], 0)]
        result = nums[0]
        for i in range(1, n):
            while heap and heap[0][1] < i - k:
                heapq.heappop(heap)
            a = -heap[0][0]
            m = nums[i] + (a if a > 0 else 0)
            heapq.heappush(heap, (-m, i))
            result = max(result, m)
        return result

from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        
        que = deque()
        for ind in range(len(nums)):
            nums[ind] += que[0] if que else 0
            
            while que and nums[ind] > que[-1]:
                que.pop()
            
            if nums[ind] > 0:
                que.append(nums[ind])
                
            if que and ind >= k and que[0] == nums[ind-k]:
                que.popleft()
                
        return max(nums)
            


from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums, k):
        #if max(nums) <= 0: return max(nums)   # optimization
        #if min(nums) >= 0: return sum(nums)   # optimization
    
        N, queue = len(nums), deque()
        dp = [val for val in nums]
        for i, val in enumerate(nums):
            if queue and (i - queue[0] > k):
                queue.popleft()
            if queue and dp[queue[0]] > 0:
                dp[i] += dp[queue[0]]
            while queue and dp[i] >= dp[queue[-1]]:
                queue.pop()
            queue.append(i)
        return  max(dp)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        q = deque()
        q.append((nums[0],0))
        max_sum = nums[0]

        for i in range(1,len(nums)):
            while q and q[0][1] < i - k:
                q.popleft()

            next_val = max(nums[i], nums[i] + q[0][0])
            
            while q and q[-1][0] < next_val:
                q.pop()

            q.append((next_val,i))

            max_sum = max(max_sum, q[0][0])

        return max_sum



class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        deque = []
        for i, num in enumerate(nums):
            while(deque and nums[deque[-1]] < 0):
                deque.pop()
            while(deque and deque[0] < i - k):
                deque.pop(0)
            if deque:
                nums[i] = nums[deque[0]] + num
            
            while(deque and nums[deque[-1]] < nums[i]):
                deque.pop()
            deque.append(i)
        
        return max(nums)

from collections import deque

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        largest = deque()
        global_max = float('-inf')

        for i, num in enumerate(nums):
            if largest and largest[-1][1] < i - k: largest.pop()

            curr = num + max(0, largest[-1][0] if largest else 0)
            while largest and curr > largest[0][0]:
                largest.popleft()
            global_max = max(global_max, curr)
            largest.appendleft((curr, i))

        return global_max

from collections import deque
class Solution:
    def constrainedSubsetSum(self, A: List[int], k: int) -> int:
        deque = collections.deque()
        for i in range(len(A)):
            A[i] += deque[0] if deque else 0
            while len(deque) and A[i] > deque[-1]:
                deque.pop()
            if A[i] > 0:
                deque.append(A[i])
            if i >= k and deque and deque[0] == A[i - k]:
                deque.popleft()
        return max(A)
            


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        q = deque()
        q.append((nums[0],0))
        max_sum = nums[0]

        for i in range(1,len(nums)):
            while q and q[0][1] < i - k:
                q.popleft()

            next_val = nums[i]

            if q and q[0][0] >= 0:
                next_val += q[0][0]
            
            while q and q[-1][0] < next_val:
                q.pop()

            q.append((next_val,i))

            max_sum = max(max_sum, q[0][0])

        return max_sum



class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp=collections.deque([(nums[0],0)])
        ans=nums[0]
        for i in range(1,len(nums)):
            new = nums[i] + max(0,dp[0][0])
            while dp and dp[0][1]<=i-k:
                dp.popleft()
            while dp and new>=dp[-1][0]:
                dp.pop()
            dp.append((new,i))
            ans=max(ans,new)
        return ans

from collections import deque
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp = [0] * len(nums)
        
        dp[0] = nums[0]
        
        ans = dp[0]
        
        # queue holds the index
        queue = deque([0])
        
        for j in range(1, len(nums)):
            if queue and queue[0] < j-k:
                queue.popleft()
                
            dp[j] = nums[j] + max(0, dp[queue[0]])
            
            while queue and dp[queue[-1]] < dp[j]:
                queue.pop()
            
            queue.append(j)
            ans = max(ans, dp[j])
            
        return ans

from collections import deque

class MaxQueue:
    def __init__(self, size):
        self.queue = deque()
        self.size = size
        
    def add(self, val, i):
        while self.queue and val > self.queue[-1][0]:
                self.queue.pop()
        self.queue.append((val, i))                            
        
        while i - self.queue[0][1] >= self.size: 
            self.queue.popleft()            

    def max(self):
        if self.queue:
            return self.queue[0][0]
        else:
            return 0

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        queue = MaxQueue(k)
        result = -1
        for i in range(len(nums)):
            score = nums[i]
            prev = queue.max()
            if prev > 0:
                score += prev
            queue.add(score, i)
            result = max(result, score)
        return result


class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        import heapq
        h = []
        heapq.heapify(h)
        largeNum = -10000000000
        ans = largeNum
        for i in range(len(nums)):
            if(i == 0):
                ans = nums[i]
                heapq.heappush(h, (-nums[i], i))
            else:
                b = False
                m,index = heapq.heappop(h)
                while(index < i-k):
                    m,index = heapq.heappop(h)
                heapq.heappush(h, (m,index))
                ans = max(ans, nums[i] - m, nums[i])
                heapq.heappush(h, (min(m-nums[i], -nums[i]), i))
            #print(h)
        #print(ans)
        return ans

import heapq
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        queue = [(-nums[0], 0)]
        res = nums[0]
        
        for i in range(1, len(nums)):
            while i - k -1 >= queue[0][1]:
                heapq.heappop(queue)
            
            curr = max(-queue[0][0], 0) + nums[i]
            res = max(res, curr)
            heapq.heappush(queue, (-curr, i))
        return res

from typing import List
import numpy

class Solution:
  def constrainedSubsetSum(self, nums: List[int], k: int) -> int:

    _len = len(nums)
    dp = numpy.zeros(_len, dtype=int)
    dp[0] = nums[0]
    _deque = []
    result = -sys.maxsize
    for i in range(_len):

      while _deque and i - _deque[0] > k:
        _deque.pop(0)

      tmp = 0
      if _deque:
        tmp = dp[_deque[0]]
      dp[i] = max(nums[i], nums[i] + tmp)
      result = max(result, dp[i])

      while _deque and dp[i] >= dp[_deque[-1]]:
        _deque.pop()

      _deque.append(i)
      pass


    return result


from sortedcontainers import SortedList
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        B = [nums[i] for i in range(len(nums))]
        store = SortedList()
        
        for i in range(len(nums)-1,-1,-1): 
            if len(store) > 0:
                if store[-1] > 0:
                    B[i] += store[-1]
            
            
            store.add(B[i])
            if len(store) > k:
                store.remove(B[i+k])

        return max(B)