#1425

Constrained Subsequence Sum

expert · 1260 · lc hard +32 · verified · 56.4% accepted · 2,241 likes · top 51%

⚑ Monotonic Deque (Sliding Window Max/Min)

Description

Given an integer array nums and an integer k, find the maximum sum of a non-empty subsequence such that any two consecutive chosen indices i < j satisfy j - i <= k. Return this maximum sum.

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].

Code

1

2

3

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

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