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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Amortized analysis

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:
		heap = []
		ans = -10001
		for (i, num) in enumerate(nums):
			while len(heap) > 0:
				(_, val, idx) = heap[0]
				if idx < i - k:
					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:
				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)
		for i in range(k, len(nums)):
			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:
				queue.popleft()
			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):
			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:
		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)


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:
		(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, nums: List[int], k: int) -> int:
		numLength = len(nums)
		maxSums = defaultdict(int)
		maxSum = nums[0]
		maxQueue = deque([0])
		for i in range(numLength - 1, -1, -1):
			ithMax = max(nums[i], maxQueue[0] + nums[i])
			maxSums[i] = ithMax
			if len(maxQueue) == k:
				if maxSums[i + k] == maxQueue[0]:
					maxQueue.popleft()
			while maxQueue and ithMax > maxQueue[-1]:
				maxQueue.pop()
			maxQueue.append(ithMax)
			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:
		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:
		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))
		return max(dp)


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]])
		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:
		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]
			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:
		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


import collections

class Solution:

	def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
		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:
		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)
		ans = nums.copy()
		q = []
		for i in range(n - 1, -1, -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:
		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, A: List[int], k: int) -> int:
		Q = deque([(0, A[0])])
		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))
		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:
		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)


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, nums: List[int], k: int) -> int:
		dp = [0] * len(nums)
		dp[0] = nums[0]
		ans = dp[0]
		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))
		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)