1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
# 1425. Constrained Subsequence Sum
import collections
"""
given an integer array 'nums' and an integer 'k', return the maximum sum of a
non-empty subsequnce of that array 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.
"""
class Solution(object):
def constrainedSubsetSum(self, nums, k):
dq = collections.deque
for i in range(len(nums)):
nums[i] += dq[0] if dq else 0
while len(dq) and nums[i] > dq[-1]:
dp.pop()
if nums[i] > 0:
dq.append(nums[i])
if i >= k and dq and dq[0] == nums[i - k]:
dq.popleft()
return max(nums)
if __name__ == "__main__":
obj = Solution()
print(obj.constrainedSubsetSum(nums=[10, 2, -10, 5, 20], k=2)) # expect: 37
print(obj.constrainedSubsetSum(nums=[-1, -2, -3], k=1)) # expect: -1
print(obj.constrainedSubsetSum(nums=[10, -2, -10, -5, 20], k=2)) # expect: 23
|