All problems

Constrained Subsequence Sum

Hard · monotonic deque

You are given a list of numbers nums (some may be negative) and a whole number k.

Choose at least one number from the list, keeping them in their original order. Any two numbers that are chosen one after the other must sit at most k positions apart in the list: if you choose the numbers at positions i and j with nothing chosen between them, then j - i <= k. Numbers in between may be skipped freely, as long as no gap is longer than k.

Return the largest possible sum of the chosen numbers.

Examples

Example 1

Input: nums = [10, 2, -10, 5, 20], k = 2

Output: 37

Choose 10, 2, 5, 20 (positions 0, 1, 3, 4). The gap from position 1 to 3 is 2, which is allowed. The sum is 37.

Example 2

Input: nums = [-1, -2, -3], k = 1

Output: -1

At least one number must be chosen, so the best is the single number -1.

Example 3

Input: nums = [3, -9, -9, 4], k = 2

Output: 4

The 3 and the 4 are three positions apart, which is more than 2, so choosing both would need a -9 between them (sum -2). The 4 on its own is best.

Constraints