347. Jump Game VI

MediumDynamic Programming

You are given a **0-indexed** integer array `nums` and an integer `k`. You are initially standing at index `0`. In one move, you can jump at most `k` steps forward without going outside the boundaries of the array. That is, you can jump from index `i` to any index in the range `[i + 1, min(n - 1, i + k)]` **inclusive**. You want to reach the last index of the array (index `n - 1`). Your **score** is the **sum** of all `nums[j]` for each index `j` you visited in the array. Return the **maximum score** you can get.

Examples

Input: [1,-1,-2,4,-7,3] 2

Output: 7

Explanation: Visit indices 0,1,3,5 → 1 + (-1) + 4 + 3 = 7 (jumps of size <= 2).

Constraints

  • 1 <= nums.length, k <= 10^5
  • -10^4 <= nums[i] <= 10^4
Loading...

Run checks all cases above. Submit evaluates all test cases.