Loading problem...
You are given a 0-indexed integer array values representing scores at each position, along with a positive integer stepLimit that defines the maximum leap distance.
Starting at position 0, your objective is to navigate to the final position (index n - 1) while accumulating the highest possible total score. At each step, you can leap forward by at least 1 and at most stepLimit positions, as long as you remain within the array boundaries.
More formally, from position i, you may leap to any position j where i + 1 ≤ j ≤ min(n - 1, i + stepLimit).
Your cumulative score equals the sum of values[j] for every position j you land on during your journey, including both the starting position and the destination.
Determine the maximum score achievable to reach the end of the array.
values = [1,-1,-2,4,-7,3]
stepLimit = 27One optimal path visits positions 0 → 1 → 3 → 5, collecting values [1, -1, 4, 3]. The total score is 1 + (-1) + 4 + 3 = 7. Notice that we strategically skip the highly negative values at positions 2 and 4 by maximizing our leaps when beneficial.
values = [10,-5,-2,4,0,3]
stepLimit = 317The optimal strategy is to leap from position 0 directly to position 3, then to position 5: path 0 → 3 → 5. This collects values [10, 4, 3] = 17. By using the maximum step limit of 3, we completely avoid the negative values at positions 1 and 2.
values = [1,-5,-20,4,-1,3,-6,-3]
stepLimit = 20Following the path 0 → 2 → 3 → 5 → 7 yields values [1, -20, 4, 3, -3] = -15. A better path is 0 → 1 → 3 → 4 → 6 → 7 with values [1, -5, 4, -1, -6, -3] = -10. The optimal path 0 → 1 → 3 → 5 → 7 achieves [1, -5, 4, 3, -3] = 0. Even with optimal choices, negative values are unavoidable in this configuration.
Constraints