All problems

Jump Game VI

Medium · monotonic deque

A row of stepping stones is laid out in a line. Stone i carries the number nums[i], which may be negative.

You start on the first stone. From stone i you can hop forward to any of the next k stones (stones i + 1 up to i + k, as long as they exist). You must finish on the last stone.

Your score is the sum of the numbers on every stone you land on, including the first and the last. Return the highest score you can get.

If there is only one stone, you are already standing on both the first and the last stone, so the score is its number.

Examples

Example 1

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

Output: 7

One best route is the stones 1, -1, 4, 3 (positions 0, 1, 3, 5), each hop at most 2 long: 1 - 1 + 4 + 3 = 7.

Example 2

Input: nums = [10, -5, -2, 4, 0, 3], k = 3

Output: 17

Hop from position 0 straight to position 3, then to position 5: 10 + 4 + 3 = 17. Landing on the 0 as well scores the same.

Example 3

Input: nums = [5], k = 1

Output: 5

There is only one stone.

Constraints