3418. Maximum Amount of Money Robot Can Earn

Array
Matrix
Dynamic Programming

TIME

O(m × n)

SPACE

O(m × n)

Intuition

Standard grid DP with an extra dimension: we can neutralize up to 2 negative cells. Track how many neutralizations have been used at each position.

Solution

State Definition

dp[i][j][k] = maximum coins at cell (i, j) with k neutralizations used (k = 0, 1, or 2)

Transitions

For each cell (i, j) with value val, coming from top or left:

Option 1: Don't neutralize

dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k]) + val

Option 2: Neutralize (only if val < 0 and k > 0)

dp[i][j][k] = max(dp[i-1][j][k-1], dp[i][j-1][k-1]) + 0

Base Case

At (0, 0):

If coins[0][0] >= 0: all states start with coins[0][0]
If coins[0][0] < 0:
- dp[0][0][0] = coins[0][0] (no neutralize)
- dp[0][0][1] = dp[0][0][2] = 0 (neutralize)

Answer

max(dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2])

Complexity

Time: O(m × n × 3) = O(m × n)
Space: O(m × n × 3) = O(m × n)

Edge Cases

All positive values → no need to neutralize
All negative values → neutralize the 2 largest losses
Single cell grid
Start or end cell is negative

Code

from typing import List


class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        """
        3418. Maximum Amount of Money Robot Can Earn
        Time: O(m × n)
        Space: O(m × n)
        """
        m, n = len(coins), len(coins[0])

        dp = [[[float('-inf')] * 3 for _ in range(n)] for _ in range(m)]

        if coins[0][0] >= 0:
            for k in range(3):
                dp[0][0][k] = coins[0][0]
        else:
            dp[0][0][0] = coins[0][0]
            dp[0][0][1] = 0
            dp[0][0][2] = 0

        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue

                for k in range(3):
                    best_prev = float('-inf')

                    if i > 0:
                        best_prev = max(best_prev, dp[i - 1][j][k])
                    if j > 0:
                        best_prev = max(best_prev, dp[i][j - 1][k])

                    if best_prev == float('-inf'):
                        continue

                    val = coins[i][j]

                    dp[i][j][k] = max(dp[i][j][k], best_prev + val)

                    if val < 0 and k > 0:
                        best_prev_k_minus = float('-inf')
                        if i > 0:
                            best_prev_k_minus = max(best_prev_k_minus, dp[i - 1][j][k - 1])
                        if j > 0:
                            best_prev_k_minus = max(best_prev_k_minus, dp[i][j - 1][k - 1])

                        dp[i][j][k] = max(dp[i][j][k], best_prev_k_minus)

        return max(dp[m - 1][n - 1])

/**
 * 3418. Maximum Amount of Money Robot Can Earn
 * Time: O(m × n)
 * Space: O(m × n)
 */
class Solution {
    public int maximumAmount(int[][] coins) {
        int m = coins.length, n = coins[0].length;

        int[][][] dp = new int[m][n][3];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 3; k++) {
                    dp[i][j][k] = Integer.MIN_VALUE / 2;
                }
            }
        }

        if (coins[0][0] >= 0) {
            for (int k = 0; k < 3; k++) {
                dp[0][0][k] = coins[0][0];
            }
        } else {
            dp[0][0][0] = coins[0][0];
            dp[0][0][1] = 0;
            dp[0][0][2] = 0;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;

                for (int k = 0; k < 3; k++) {
                    int val = coins[i][j];

                    if (i > 0) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j][k] + val);
                    }

                    if (j > 0) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i][j - 1][k] + val);
                    }

                    if (val < 0 && k > 0) {
                        if (i > 0) {
                            dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j][k - 1]);
                        }
                        if (j > 0) {
                            dp[i][j][k] = Math.max(dp[i][j][k], dp[i][j - 1][k - 1]);
                        }
                    }
                }
            }
        }

        return Math.max(dp[m - 1][n - 1][0],
                Math.max(dp[m - 1][n - 1][1], dp[m - 1][n - 1][2]));
    }
}