Show problems as
Classic problem #1696MediumArrayDynamic ProgrammingQueueHeap (Priority Queue)Monotonic Queue

Jump Game VI

Real-world version: Hopping Along the Row of Pads
Tracked in this browser only
Read Jump Game VI on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A row of pads holds the scores scores. You begin on the first pad and must finish on the last one. From a pad you may hop forward to any pad at most k places ahead, so long as it is still on the row.

Your total is the sum of the scores of every pad you stand on, counting the first and the last.

Return the largest total possible.

Examples

Example 1

Input
scores = [1, -100, 2], k = 2
Output
3

A hop of two places clears the heavy loss in the middle, so only the two ends are stood on.

Example 2

Input
scores = [1, -100, 2], k = 1
Output
-97

A hop of one place forces every pad to be stood on, the loss included.

Example 3

Input
scores = [1, 2, 3, 4, 5], k = 2
Output
15

Every pad scores something, so standing on all of them is best, and hops of one place manage exactly that.

Constraints

  • 1 <= scores.length <= 10^5
  • 1 <= k <= 10^5
  • -10^4 <= scores[i] <= 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_result(scores: list[int], k: int) -> int:
Java
public int maxResult(int[] scores, int k)

More on the same topics