623. Jump Game VI (DP + Monotonic Deque)

Starting at index 0 of nums, in one move you may jump forward from i to any index in [i+1, i+k]. Your score is the sum of nums values on visited indices. Return the maximum score to reach the last index. The input is JSON {nums, k}.

Input: JSON {nums, k}.

Output: Integer — the maximum score.

Examples

Input: {"nums":[1,-1,-2,4,-7,3],"k":2}
Output: 7
Explanation: 1 -> -1 -> 4 -> 3 = 7.

Input: {"nums":[10,-5,-2,4,0,3],"k":3}
Output: 17
Explanation: Best reachable score.

Input: {"nums":[5],"k":1}
Output: 5
Explanation: Already at the end.

Constraints

• 1<=k<=n<=10^5

Asked by