644. Constrained Subsequence Sum

MediumStackDequeDynamic Programming

Given an array nums and an integer k, return the maximum sum of a non-empty subsequence such that every two consecutive chosen elements are at most k indices apart in the original array. The input is JSON {nums, k}.

Input: JSON {nums, k}.

Output: Integer — the maximum constrained subsequence sum.

Examples

Example 1
Input: {"nums":[10,2,-10,5,20],"k":2}
Output: 37
Explanation: 10 + 2 + 5 + 20.
Example 2
Input: {"nums":[-1,-2,-3],"k":1}
Output: -1
Explanation: Pick the largest single element.
Example 3
Input: {"nums":[10,-2,-10,-5,20],"k":2}
Output: 23
Explanation: 10 - 5 + ... best chain.

Constraints

Asked by

Google
Solve this problem in the editor →