LeetCode 1425. [Python] Constrained Subsequence Sum
原题链接
困难
作者:
徐辰潇
,
2020-12-23 22:38:55
,
所有人可见
,
阅读 572
class Solution:
def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
#TC: O(len(nums))
#SC: O(len(nums))
#Similar to question 1696
res = nums[0]
Dp = [0]*len(nums)
Dp[0] = max(0,nums[0])
DQ = collections.deque([0])
for i in range(1, len(nums)):
while(len(DQ) > 0 and i - DQ[0] > k):
DQ.popleft()
Dp[i] = nums[i] + max(0,Dp[DQ[0]])
res = max(res, Dp[i])
while(len(DQ) > 0 and Dp[i] >= Dp[DQ[-1]]):
DQ.pop()
DQ.append(i)
return res