Frontend School

Path to Maximize Gold

DSA
medium

Path to Maximize Gold

Medium
Dynamic Programming
1D DP
Arrays

Overview

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.

What you need to do / Task

Implement the function maximizeGold that calculates the maximum total gold you can collect by traversing the mine shaft from the start to the end.

  1. From any given section i, you can move to either section i+1 (the immediately next section) or section i+2 (skipping one section).
  2. You must always move forward.
  3. Your path must eventually 'land on' the last section of the shaft (index n-1).
  4. The total gold collected is the sum of gold values from all sections you land on along your chosen path, including the starting section and the final section.

Input & output

  • Input: gold: number[]
    • An array of integers where gold[i] represents the amount of gold (or cost) in the i-th section of the mine shaft.
  • Output: number
    • The maximum total gold that can be collected following the rules.

Clarifications

  • If the gold array contains only one element, you are already at the end, and the total gold is that single element's value.
  • Yes, 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.
  • You must always move forward and eventually 'land on' the last section of the shaft (gold[n-1]). The goal is to maximize the total gold collected up to and including the last section.

Examples

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= gold.length <= 10^5
  • -1000 <= gold[i] <= 1000

Out of scope

  • Optimizing space complexity beyond O(N) (O(N) for the DP table is acceptable).
  • Handling non-linear mine layouts or more complex jump mechanics (e.g., variable jump lengths, conditional jumps).

What interviewers evaluate

  • Correct identification and definition of the dynamic programming state and recurrence relation.
  • Accurate handling of base cases and array boundary conditions.
  • Efficient implementation achieving the optimal time complexity.
  • Clarity, readability, and overall structure of the code.

Loading editor...