Hard

Quiz

#1425 Constrained Subsequence Sum

APPROACH

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

1 of 4

1:00

What is the optimal approach for this problem?