Maximum Path Points on Stepping Stones
Imagine you are a treasure hunter navigating a treacherous path made of stepping stones. Each stone has a certain number of points you can collect by landing on it. To make progress, you can only jump a short distance: either to the very next stone, or skip one stone and jump to the stone after that. Your mission is to find the path from the starting stone to the final stone that yields the maximum total points.
This problem evaluates your ability to model sequential decision-making using dynamic programming, a fundamental technique for optimizing over overlapping subproblems.
Your task is to implement a function maxPathPoints that calculates the maximum total points achievable when traversing a path of stepping stones.
maxPathPoints function.Input:
stones: An array of integers, stones[i] represents the points gained by landing on the i-th stone. The path starts at stones[0] and ends at stones[n-1].Output:
stones[n-1]).Function Signature (TypeScript):
function maxPathPoints(stones: number[]): number
stones[0]) and the ending stone (stones[n-1]).stones contains negative values? The problem constraints will specify stones[i] >= 0.Examples
Example 1
Input:
stones = [10, 20, 30, 40]
Output:
100
Note:
To reach stone 0: 10 To reach stone 1 (from 0): 10 + 20 = 30 To reach stone 2 (from max of reaching 0 or 1): 30 + max(10, 30) = 60 To reach stone 3 (from max of reaching 1 or 2): 40 + max(30, 60) = 100 Maximum points collected is 100.
Example 2
Input:
stones = [5]
Output:
5
Note:
With only one stone, you start and end on it, collecting its points.
Example 3
Input:
stones = [100, 1, 1, 100]
Output:
202
Note:
To reach stone 0: 100 To reach stone 1 (from 0): 100 + 1 = 101 To reach stone 2 (from max of reaching 0 or 1): 1 + max(100, 101) = 102 To reach stone 3 (from max of reaching 1 or 2): 100 + max(101, 102) = 202 Maximum points collected is 202.
Constraints
1 <= stones.length <= 10^5 (denoted as n)0 <= stones[i] <= 1000Loading editor...