LeetCode 3418 - Maximum Amount of Money Robot Can Earn

We are given an m x n grid where each cell contains either a positive value, zero, or a negative value. The robot starts at the top-left cell (0, 0) and must reach the bottom-right cell (m - 1, n - 1).

leetcodemediumarraydynamic-programmingmatrix

LeetCode Problem 3418

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

We are given an m x n grid where each cell contains either a positive value, zero, or a negative value.

The robot starts at the top-left cell (0, 0) and must reach the bottom-right cell (m - 1, n - 1). At every step it may only move either right or down, so every valid route is a monotonic path through the grid.

Each cell affects the robot's profit:

  • A non-negative value adds coins to the robot's total.
  • A negative value represents a robber. Entering that cell normally decreases the total by the absolute value of the number, which is equivalent to adding the negative value.

The special twist is that the robot may neutralize robbers in at most two cells along its path. If a robber is neutralized, the loss from that cell becomes zero instead of a negative amount.

The goal is to maximize the final profit when the robot reaches the destination. The final profit is allowed to be negative.

The input is a matrix coins, where coins[i][j] represents the gain or loss associated with cell (i, j). The output is a single integer, the maximum achievable profit. We are given an m x n grid coins, where each cell contributes either a gain or a loss to the robot's total money.

The robot starts at position (0, 0) and must reach (m - 1, n - 1). At every step it may move only:

  • one cell to the right, or
  • one cell downward.

If a cell contains a nonnegative value, that amount is added to the robot's total. If a cell contains a negative value, the robot loses the corresponding number of coins.

The special feature of the problem is that the robot may neutralize at most two robbers along its path. Neutralizing a robber means that when the robot enters a negative-valued cell, it may choose to ignore that loss entirely, treating the contribution of that cell as 0.

The objective is to maximize the final amount of money collected along the chosen path.

The constraints are important:

  • m, n <= 500
  • The grid can contain up to 500 * 500 = 250,000 cells.
  • Values range from -1000 to 1000.

A brute-force path search is immediately infeasible because the number of paths grows exponentially. The constraints strongly suggest a dynamic programming solution with a small state space.

Several edge cases deserve attention:

  • The starting cell itself may contain a robber.
  • The ending cell may contain a robber.
  • Every cell may be negative.
  • The optimal path may intentionally save neutralizations for larger losses later.
  • The answer may be negative, so using 0 as an initial DP value would be incorrect.
  • The grid may contain up to 250,000 cells.
  • Cell values are between -1000 and 1000.

A naive path enumeration is impossible because the number of right/down paths grows exponentially. Any solution must process each cell only a constant number of times.

Several edge cases deserve attention:

  • The starting cell may itself contain a robber.
  • The ending cell may contain a robber.
  • All values may be negative.
  • The optimal solution may use zero, one, or two neutralizations.
  • The maximum profit can be negative, so we cannot initialize DP states with 0.

Approaches

Brute Force

A straightforward approach is to enumerate every possible path from the top-left corner to the bottom-right corner.

For each path, we could collect all visited values, determine which two negative cells should be neutralized, compute the resulting profit, and keep the maximum.

This approach is correct because it explicitly examines every possible route and every possible use of the neutralizations.

Unfortunately, the number of paths is enormous:

$$\binom{m+n-2}{m-1}$$

For grids as large as 500 x 500, this is completely impractical.

Key Insight

The important observation is that the future only depends on three pieces of information:

  • Current row.
  • Current column.
  • How many neutralizations have already been used.

The exact path taken to reach a cell does not matter. Only the best profit achieved for each neutralization count matters.

This naturally leads to dynamic programming.

Define:

dp[i][j][k]

as the maximum profit obtainable when reaching cell (i, j) after using exactly k neutralizations, where k ∈ {0,1,2}.

For a positive cell, we simply add its value.

For a negative cell, we have two choices:

  • Accept the loss.
  • Use a neutralization if one is still available.

Since only three neutralization states exist, each cell requires only constant work.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Enumerates all paths
Optimal Dynamic Programming O(mn) O(n) Tracks position and neutralizations used

Algorithm Walkthrough

Optimal DP with Rolling Arrays

  1. Define three DP states for every cell, representing the best profit after using 0, 1, or 2 neutralizations.
  2. Observe that each cell only depends on the cell directly above and directly to the left. Therefore, we do not need the entire m x n x 3 DP table.
  3. Maintain a rolling DP array for the previous row. Each column stores three values corresponding to the three neutralization states.
  4. Process the grid row by row and left to right.
  5. For each cell, determine the best predecessor state for every neutralization count. The predecessor may come either from the top or from the left.
  6. If the current cell value is non-negative:
  • The value must be collected.
  • For every neutralization count k:
dp[k] = best_predecessor[k] + value
  1. If the current cell value is negative:
  • Option 1: do not neutralize the robber.
best_predecessor[k] + value
  • Option 2: neutralize the robber.
best_predecessor[k-1]
  • Take the maximum of the valid choices.
  1. Handle (0,0) separately because it has no predecessor.
  • If the starting value is positive or zero:
state[0] = value
  • If the starting value is negative:
state[0] = value
state[1] = 0

because we may immediately neutralize it. 9. Continue until the bottom-right cell is processed. 10. The answer is the maximum among the three states at the destination.

Why it works

For every cell and every neutralization count, the DP state stores the maximum achievable profit among all paths reaching that configuration. Every valid path must enter a cell either from above or from the left, and every interaction with a robber is represented by either consuming a neutralization or accepting the loss. Since all possibilities are considered and only the best profit is retained, the DP invariant guarantees that the final state contains the optimal answer. A brute-force solution would enumerate every valid path from the top-left corner to the bottom-right corner.

For each path, we would determine which negative cells should be neutralized. Since at most two neutralizations are allowed, we could try every possible choice of up to two robber cells on that path and compute the resulting profit.

This approach is correct because it explicitly examines every feasible solution. However, it is completely impractical. The number of paths is

$$\binom{m+n-2}{m-1},$$

which is exponential in the grid dimensions. Even for moderate grid sizes, the number of paths becomes enormous.

Optimal Dynamic Programming

The key observation is that the future only depends on:

  • the current cell (i, j),
  • how many neutralizations have already been used.

The exact path taken before reaching (i, j) is irrelevant once we know the maximum profit achievable for each neutralization count.

Therefore, define a DP state:

$$dp[i][j][k]$$

as the maximum profit obtainable upon reaching cell (i,j) after using exactly k neutralizations, where k ∈ {0,1,2}.

For each cell, we only need to consider transitions from:

  • the cell above,
  • the cell to the left.

If the current value is nonnegative, it must be collected.

If the current value is negative, we have two choices:

  • accept the loss,
  • neutralize it (if fewer than two neutralizations have been used).

Since there are only three possible values of k, each cell requires only constant work.

Because m and n can each be 500, we further compress the DP to a rolling row, reducing memory from O(mn) to O(n).

Comparison of Approaches

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Enumerates all paths and neutralization choices
Optimal DP O(mn) O(n) Tracks best profit for each neutralization count

Algorithm Walkthrough

  1. Let dp[j][k] represent the maximum profit for the current row at column j after using exactly k neutralizations.
  2. Initialize every state to negative infinity. This is necessary because valid profits may themselves be negative.
  3. Process the grid row by row and column by column.
  4. For each cell (i, j), gather all reachable states from:
  • the cell above, stored in the previous row DP,
  • the cell to the left, already computed in the current row.
  1. For every incoming state with k neutralizations already used:
  • Add the cell value normally, producing a state with the same k.
  • If the cell value is negative and k < 2, also consider neutralizing it, producing a state with k + 1 neutralizations and adding 0 instead of the negative value.
  1. The start cell (0,0) is handled similarly:
  • Take its value normally.
  • If it is negative, optionally neutralize it immediately.
  1. After processing all cells, the answer is the maximum among the three states at the bottom-right corner.

Why it works

The DP invariant is:

$$dp[i][j][k]$$

stores the maximum profit achievable when reaching (i,j) having used exactly k neutralizations.

Every valid path to (i,j) must arrive either from above or from the left. The transition considers both possibilities and also considers every legal decision regarding neutralization at the current cell. Therefore every feasible solution is represented, and the maximum profit among them is preserved.

By induction over the processing order of cells, every DP state is correct. Consequently, the maximum value at the destination is the optimal answer.

Python Solution

from typing import List

class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        m, n = len(coins), len(coins[0])
        NEG_INF = -10**18

        prev_row = [[NEG_INF] * 3 for _ in range(n)]

        for i in range(m):
            curr_row = [[NEG_INF] * 3 for _ in range(n)]
        prev = [[NEG_INF] * 3 for _ in range(n)]

        for i in range(m):
            curr = [[NEG_INF] * 3 for _ in range(n)]

            for j in range(n):
                val = coins[i][j]

                if i == 0 and j == 0:
                    if val >= 0:
                        curr_row[j][0] = val
                    else:
                        curr_row[j][0] = val
                        curr_row[j][1] = 0
                    continue

                top = prev_row[j] if i > 0 else [NEG_INF] * 3
                left = curr_row[j - 1] if j > 0 else [NEG_INF] * 3

                best_prev = [
                    max(top[0], left[0]),
                    max(top[1], left[1]),
                    max(top[2], left[2]),
                ]

                if val >= 0:
                    for k in range(3):
                        if best_prev[k] != NEG_INF:
                            curr_row[j][k] = best_prev[k] + val
                else:
                    for k in range(3):
                        if best_prev[k] != NEG_INF:
                            curr_row[j][k] = max(
                                curr_row[j][k],
                                best_prev[k] + val
                            )

                        if k > 0 and best_prev[k - 1] != NEG_INF:
                            curr_row[j][k] = max(
                                curr_row[j][k],
                                best_prev[k - 1]
                            )

            prev_row = curr_row

        return max(prev_row[n - 1])

The implementation stores only one DP row at a time. Each entry contains three values corresponding to using 0, 1, or 2 neutralizations.

For every cell, we compute the best predecessor profit for each neutralization count by comparing the top and left states. Positive cells simply add their value. Negative cells consider both possibilities, accepting the loss or spending a neutralization.

The starting cell is initialized separately because it has no predecessor. Finally, the maximum value among the three destination states is returned. curr[j][0] = val if val < 0: curr[j][1] = 0 continue

            sources = []

            if i > 0:
                sources.append(prev[j])

            if j > 0:
                sources.append(curr[j - 1])

            for src in sources:
                for used in range(3):
                    if src[used] == NEG_INF:
                        continue

                    # Do not neutralize.
                    curr[j][used] = max(
                        curr[j][used],
                        src[used] + val
                    )

                    # Neutralize current robber.
                    if val < 0 and used < 2:
                        curr[j][used + 1] = max(
                            curr[j][used + 1],
                            src[used]
                        )

        prev = curr

    return max(prev[n - 1])


The implementation uses rolling-row dynamic programming. `prev` stores DP values for the previous row, while `curr` stores values for the current row.

Each DP entry contains three states corresponding to using `0`, `1`, or `2` neutralizations. For every reachable state, we either accept the current cell value or, if the cell is negative and neutralizations remain, neutralize the robber and keep the previous profit unchanged.

The start cell is initialized separately because it has no predecessors.

After processing all rows, the destination cell contains three possible profits corresponding to different numbers of neutralizations used. The maximum of those values is returned.

## Go Solution

```go
func maximumAmount(coins [][]int) int {
	m := len(coins)
	n := len(coins[0])

	const NEG_INF int = -1 << 60

	prevRow := make([][3]int, n)
	for j := 0; j < n; j++ {
		for k := 0; k < 3; k++ {
			prevRow[j][k] = NEG_INF
	const NEG_INF = -1 << 60

	prev := make([][3]int, n)
	for j := 0; j < n; j++ {
		for k := 0; k < 3; k++ {
			prev[j][k] = NEG_INF
		}
	}

	for i := 0; i < m; i++ {
		currRow := make([][3]int, n)
		for j := 0; j < n; j++ {
			for k := 0; k < 3; k++ {
				currRow[j][k] = NEG_INF
		curr := make([][3]int, n)
		for j := 0; j < n; j++ {
			for k := 0; k < 3; k++ {
				curr[j][k] = NEG_INF
			}
		}

		for j := 0; j < n; j++ {
			val := coins[i][j]

			if i == 0 && j == 0 {
				if val >= 0 {
					currRow[j][0] = val
				} else {
					currRow[j][0] = val
					currRow[j][1] = 0
				curr[j][0] = val
				if val < 0 {
					curr[j][1] = 0
				}
				continue
			}

			var top, left [3]int

			for k := 0; k < 3; k++ {
				top[k] = NEG_INF
				left[k] = NEG_INF
			}

			if i > 0 {
				top = prevRow[j]
			}
			if j > 0 {
				left = currRow[j-1]
			}

			var bestPrev [3]int
			for k := 0; k < 3; k++ {
				if top[k] > left[k] {
					bestPrev[k] = top[k]
				} else {
					bestPrev[k] = left[k]
				}
			}

			if val >= 0 {
				for k := 0; k < 3; k++ {
					if bestPrev[k] != NEG_INF {
						currRow[j][k] = bestPrev[k] + val
					}
				}
			} else {
				for k := 0; k < 3; k++ {
					if bestPrev[k] != NEG_INF {
						candidate := bestPrev[k] + val
						if candidate > currRow[j][k] {
							currRow[j][k] = candidate
						}
					}

					if k > 0 && bestPrev[k-1] != NEG_INF {
						if bestPrev[k-1] > currRow[j][k] {
							currRow[j][k] = bestPrev[k-1]
						}
					}
				}
			}
		}

		prevRow = currRow
	}

	ans := prevRow[n-1][0]
	for k := 1; k < 3; k++ {
		if prevRow[n-1][k] > ans {
			ans = prevRow[n-1][k]
			process := func(src [3]int) {
				for used := 0; used < 3; used++ {
					if src[used] == NEG_INF {
						continue
					}

					if src[used]+val > curr[j][used] {
						curr[j][used] = src[used] + val
					}

					if val < 0 && used < 2 {
						if src[used] > curr[j][used+1] {
							curr[j][used+1] = src[used]
						}
					}
				}
			}

			if i > 0 {
				process(prev[j])
			}

			if j > 0 {
				process(curr[j-1])
			}
		}

		prev = curr
	}

	ans := prev[n-1][0]
	for k := 1; k < 3; k++ {
		if prev[n-1][k] > ans {
			ans = prev[n-1][k]
		}
	}

	return ans
}

The Go version mirrors the Python solution exactly. Fixed-size arrays of length three are used for the neutralization states, which avoids additional allocations. The sentinel value NEG_INF safely represents unreachable states. The Go implementation mirrors the Python solution exactly. Fixed-size arrays [3]int are used for the neutralization states, which avoids extra allocations and keeps the implementation efficient. The chosen negative infinity value is safely below any achievable profit.

Worked Examples

Example 1

Input:

[
 [0, 1, -1],
 [1, -2, 3],
 [2, -3, 4]
]

We track:

  • State 0 = used 0 neutralizations
  • State 1 = used 1 neutralization
  • State 2 = used 2 neutralizations

After processing each cell:

Cell States [0,1,2]
(0,0)=0 [0,-∞,-∞]
(0,1)=1 [1,-∞,-∞]
(0,2)=-1 [0,1,-∞]
(1,0)=1 [1,-∞,-∞]
(1,1)=-2 [-1,1,-∞]
(1,2)=3 [3,4,-∞]
(2,0)=2 [3,-∞,-∞]
(2,1)=-3 [0,3,-∞]
(2,2)=4 [7,8,-∞]

Destination states:

[7, 8, -∞]
We track three states:

[k=0, k=1, k=2]


#### Cell (0,0)

value = 0

[0, -∞, -∞]


#### Cell (0,1)

```sql
From left:

[1, -∞, -∞]

Cell (0,2)

value = -1

Take loss:
[0, -∞, -∞]

Neutralize:
[-, 1, -∞]

Result:

[0, 1, -∞]

Cell (1,1)

Using paths from above and left:

[ -1, 1, -∞ ]

The state 1 corresponds to neutralizing the robber at -2.

Cell (1,2)

[3, 4, 4]

Cell (2,2)

[7, 8, 8]

Answer:

8
max(7, 8, 8) = 8

Example 2

Input:

[
 [10,10,10],
 [10,10,10]
]

Every value is positive, so neutralizations are never used.

Cell States [0,1,2]
(0,0) [10,-∞,-∞]
(0,1) [20,-∞,-∞]
(0,2) [30,-∞,-∞]
(1,0) [20,-∞,-∞]
(1,1) [30,-∞,-∞]
(1,2) [40,-∞,-∞]
Since all values are positive, no neutralization is ever useful.
Cell Best Profit
(0,0) 10
(0,1) 20
(0,2) 30
(1,2) 40

Answer:

40

Complexity Analysis

Measure Complexity Explanation
Time O(mn) Each cell processes exactly 3 DP states
Space O(n) Rolling row DP stores only one row of 3-state vectors

The key observation is that each cell performs only constant work because there are exactly three neutralization states. Rolling arrays eliminate the need for storing all previous rows, reducing space from O(mn) to O(n). | Time | O(mn) | Each cell processes only 3 neutralization states | | Space | O(n) | Rolling-row DP stores only one row of states |

The DP performs a constant amount of work for each cell. Since there are m * n cells and only three neutralization counts, the running time is linear in the size of the grid. Memory usage is reduced to one row of DP values, giving O(n) auxiliary space.

Test Cases

sol = Solution()

assert sol.maximumAmount([[0,1,-1],[1,-2,3],[2,-3,4]]) == 8  # example 1

assert sol.maximumAmount([[10,10,10],[10,10,10]]) == 40  # example 2

assert sol.maximumAmount([[-5]]) == 0  # neutralize starting robber

assert sol.maximumAmount([[7]]) == 7  # single positive cell

assert sol.maximumAmount([[-1,-2,-3]]) == -1  # use two neutralizations

assert sol.maximumAmount([[-1],[-2],[-3]]) == -1  # vertical path only

assert sol.maximumAmount([[1,-100,1]]) == 2  # neutralize large loss

assert sol.maximumAmount([[1,-5,-10,1]]) == 2  # choose best two robber cells

assert sol.maximumAmount([
    [-100, 1],
    [1, 1]
]) == 2  # neutralize starting cell

assert sol.maximumAmount([
    [5, -100],
    [-100, 5]
]) == 10  # destination reachable with one neutralization

assert sol.maximumAmount([
    [-10, -20],
    [-30, -40]
]) == -10  # all negative values

assert sol.maximumAmount([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]) == 29  # all positive grid
s = Solution()

assert s.maximumAmount([[0,1,-1],[1,-2,3],[2,-3,4]]) == 8  # provided example
assert s.maximumAmount([[10,10,10],[10,10,10]]) == 40  # all positive

assert s.maximumAmount([[-5]]) == 0  # neutralize starting cell
assert s.maximumAmount([[7]]) == 7  # single positive cell

assert s.maximumAmount([[-1,-2,-3]]) == -1  # use two neutralizations on a row
assert s.maximumAmount([[-1],[-2],[-3]]) == -1  # use two neutralizations on a column

assert s.maximumAmount([[1,-100,1]]) == 2  # neutralize large loss
assert s.maximumAmount([[1,-100,-100,1]]) == 2  # neutralize two losses

assert s.maximumAmount([
    [1, -10],
    [-10, 1]
]) == 2  # one robber on any path can be neutralized

assert s.maximumAmount([
    [-10, -10],
    [-10, -10]
]) == -10  # must absorb one of the four losses

assert s.maximumAmount([
    [5, -100, 5],
    [5, 5, 5]
]) == 20  # optimal path avoids robber entirely

assert s.maximumAmount([
    [0, -5, 10],
    [-5, -5, 10],
    [10, 10, 10]
]) == 30  # mix of path choice and neutralization

Test Summary

Test Why
Example 1 Official mixed positive and negative case
Example 2 All positive values
Single negative cell Start cell neutralization
Single positive cell Minimum valid input
Single row negatives Linear path with neutralizations
Single column negatives Vertical path handling
Large negative in middle Neutralization decision
Multiple robbers Optimal neutralization placement
Negative start Special initialization case
Negative alternatives Path selection and neutralization
All negative grid Negative final answer
All positive grid Standard path DP
Example 1 Official example with neutralization
Example 2 Official example with no robbers
[[-5]] Negative starting cell
[[7]] Positive single cell
Single-row negatives Uses both neutralizations
Single-column negatives Boundary dimension case
[1,-100,1] One large robber
[1,-100,-100,1] Exactly two neutralizations
[[1,-10],[-10,1]] Multiple equivalent paths
All negative 2×2 Profit remains negative
Path avoids robber Routing can beat neutralization
Mixed grid Combination of both decisions

Edge Cases

Negative Starting Cell

The starting cell may itself contain a robber. A common bug is to assume neutralizations are only applied after movement begins. In reality, the robot enters the starting cell immediately. The implementation explicitly initializes both possibilities:

  • Accept the loss.
  • Use one neutralization immediately.

This guarantees correct handling of grids such as [[-5]].

All Cells Are Negative

Some implementations incorrectly assume the answer must be non-negative because neutralizations exist. That is not true. If there are more than two robber cells on every path, some losses must still be taken.

Using a large negative sentinel value instead of zero ensures that negative profits are preserved correctly throughout the DP.

Destination Cell Is Negative

The final cell may contain a robber. It is easy to forget that neutralizations can be used there as well. Since every cell is processed uniformly, including the destination, the DP naturally considers both taking the loss and neutralizing it, ensuring the optimal result is returned. The starting cell contributes to the path just like any other cell. A common mistake is to begin the DP after (0,0) and forget that the starting robber may itself be neutralized. The implementation explicitly initializes both possibilities:

  • take the loss,
  • neutralize immediately if the value is negative.

All Values Negative

When every cell is negative, the optimal result may still be negative because only two robbers can be neutralized. Implementations that initialize DP values to 0 incorrectly assume nonnegative profits. This solution uses negative infinity for unreachable states, preserving correctness when all feasible profits are negative.

Destination Cell Is Negative

The final cell may contain a robber. Some implementations only apply neutralization while moving and forget that the destination cell itself can be neutralized. Since every cell is processed uniformly, the destination cell receives exactly the same treatment as every other cell, ensuring the final robber can be neutralized if beneficial and if a neutralization remains available.