aboutsummaryrefslogtreecommitdiff
path: root/constrained_subseq_sum.py
blob: 95305b778095326c310e506678e8f37f7773f21c (plain)
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