404. Leap Score
A row of stepping stones is laid across a pond, and stone i carries a score nums[i] that may be negative. A frog stands on stone 0 and wants to reach the last stone. From stone i it can jump to any stone i + 1, i + 2, ..., i + k (never past the last stone).
The frog's score is the sum of the values of every stone it stands on, including the first and the last one. Return the maximum possible score. Trying every jump from every stone costs O(n * k), which is too slow when both are large; think about keeping the best candidates for the next stone in a structure that supports sliding.
Example 1
- Input:
- nums = [3,-5,4,-2,6,-1], k = 2
- Output:
- 12
- Explanation:
Jump 0 to 2 to 4 to 5: 3 + 4 + 6 + (-1) = 12, which is the best.
Example 2
- Input:
- nums = [2,-9,-9,5], k = 2
- Output:
- -2
- Explanation:
To reach stone 3 the frog must stand on stone 1 or 2, both worth -9, so the best score is 2 - 9 + 5 = -2.
Constraints
1 ≤ nums.length ≤ 105
-104 ≤ nums[i] ≤ 104
1 ≤ k ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)