Path to Maximize Gold
You are a prospector navigating a linear mine shaft. Each section of the shaft contains a certain amount of gold, which can be positive or negative (representing a 'trap' or cost). You start at the very beginning of the shaft (index 0) and aim to reach the very end, collecting as much gold as possible along your path.
This problem challenges your ability to model sequential decision-making using dynamic programming, considering optimal choices at each step to achieve a global maximum.
Implement the function maximizeGold that calculates the maximum total gold you can collect by traversing the mine shaft from the start to the end.
i, you can move to either section i+1 (the immediately next section) or section i+2 (skipping one section).n-1).gold: number[]
gold[i] represents the amount of gold (or cost) in the i-th section of the mine shaft.number
gold array contains only one element, you are already at the end, and the total gold is that single element's value.gold[i] can be negative, representing 'trap' sections that reduce your total gold. You should still find the path that yields the highest possible total, even if that total is negative.gold[n-1]). The goal is to maximize the total gold collected up to and including the last section.Examples
Example 1
Input:
gold = [1, 2, 3]
Output:
6
Note:
Path: 1 (index 0) -> 2 (index 1) -> 3 (index 2). Total: 1 + 2 + 3 = 6. This is the only path that visits all cells. The other path 1 (index 0) -> 3 (index 2) yields 1 + 3 = 4, which is less.
Example 2
Input:
gold = [10, -5, 20, -10]
Output:
30
Note:
Path: 10 (index 0) -> 20 (index 2). Total: 10 + 20 = 30. If we went 10 -> -5 -> -10, it would be 10 - 5 - 10 = -5. If we went 10 -> -5 -> 20 -> -10, it would be 10 - 5 + 20 - 10 = 15.
Example 3
Input:
gold = [-1, -2, -3]
Output:
-4
Note:
Path: -1 (index 0) -> -2 (index 1) -> -3 (index 2). Total: -1 + -2 + -3 = -6. Path: -1 (index 0) -> -3 (index 2). Total: -1 + -3 = -4. The maximum gold collected is -4.
Constraints
1 <= gold.length <= 10^5-1000 <= gold[i] <= 1000Loading editor...