Maximum Amount of Money Robot Can Earn

Medium
1673.

Maximum Amount of Money Robot Can Earn

Maximum Amount of Money Robot Can Earn is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon and Google interviews.

A robot starts at the top-left corner (0, 0) of an m x n grid coins and must reach the bottom-right corner (m - 1, n - 1), moving only right or down.

When the robot enters a cell (including the first and the last) with value coins[i][j]:

  • if coins[i][j] >= 0, it gains that many coins;
  • if coins[i][j] < 0, a robber there takes |coins[i][j]| coins.

The robot may neutralize the robbers in at most 2 cells of its path; a neutralized cell takes nothing. The robot's total may become negative.

Return the maximum total the robot can end with.

Example 1

Input
coins = [[0,1,-1],[1,-2,3],[2,-3,4]]
Output
8
Explanation
Path 0 → 1 → -2 → 3 → 4, neutralizing the -2: 0 + 1 + 0 + 3 + 4 = 8.

Example 2

Input
coins = [[10,10,10],[10,10,10]]
Output
40
Explanation
Every path collects 10 four times.

Example 3

Input
coins = [[-5]]
Output
0
Explanation
The single robber is neutralized.

Constraints

  • m == coins.length
  • n == coins[i].length
  • 1 <= m, n <= 500
  • -1000 <= coins[i][j] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} coins
 * @return {number}
 */
var maximumAmount = function(coins) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Amount of Money Robot Can Earn — Problem & Solution

Maximum Amount of Money Robot Can Earn solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Amount of Money Robot Can Earn is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming, Matrix
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A robot starts at the top-left corner (0, 0) of an m x n grid coins and must reach the bottom-right corner (m - 1, n - 1), moving only right or down.

When the robot enters a cell (including the first and the last) with value coins[i][j]:

  • if coins[i][j] >= 0, it gains that many coins;
  • if coins[i][j] < 0, a robber there takes |coins[i][j]| coins.

The robot may neutralize the robbers in at most 2 cells of its path; a neutralized cell takes nothing. The robot's total may become negative.

Return the maximum total the robot can end with.

Example 1

Input: coins = [[0,1,-1],[1,-2,3],[2,-3,4]]
Output: 8
Explanation: Path 0 → 1 → -2 → 3 → 4, neutralizing the -2: 0 + 1 + 0 + 3 + 4 = 8.

Example 2

Input: coins = [[10,10,10],[10,10,10]]
Output: 40
Explanation: Every path collects 10 four times.

Example 3

Input: coins = [[-5]]
Output: 0
Explanation: The single robber is neutralized.

Constraints

  • m == coins.length
  • n == coins[i].length
  • 1 <= m, n <= 500
  • -1000 <= coins[i][j] <= 1000

Hints for Maximum Amount of Money Robot Can Earn

  1. Hint 1

    Without the neutralizations this is the classic maximum path sum on a grid: dp[i][j] = coins[i][j] + max(dp[i - 1][j], dp[i][j - 1]).

  2. Hint 2

    The only extra information a path carries is how many neutralizations it has used — 0, 1 or 2.

  3. Hint 3

    dp[i][j][t] = best total reaching (i, j) using at most t neutralizations: either take the cell (best[t] + coins[i][j]) or, for a robber and t > 0, neutralize it (best[t - 1]).

How to solve Maximum Amount of Money Robot Can Earn

Extend the standard best-path DP with a small third dimension: the number of neutralizations used so far. With only three possible values, the table stays O(m · n).

Approach

  1. Let dp[i][j][t] be the best total on arrival at (i, j) having neutralized at most t robbers (t in 0..2).
  2. For each cell, let prev[t] be the better of the cell above and the cell to the left (or 0 for every t at the start cell).
  3. Set dp[i][j][t] = prev[t] + coins[i][j]; if coins[i][j] < 0 and t > 0, also try prev[t - 1] (neutralize this cell).
  4. Return dp[m - 1][n - 1][2].

Why it works

A path's total depends only on its cells and which of them were neutralized; the decision at a cell interacts with the future only through how many neutralizations remain. Keeping the best total for each count therefore loses no optimal path, and "at most t" makes the states monotone so the start cell can use 0 for every t.

Complexity

  • Time — O(m · n)
  • Space — O(m · n)

Pitfalls

  • The start and end cells count — a robber at (0, 0) can be neutralized too.
  • Neutralizing a non-negative cell only loses coins; only allow it for robbers (or simply never let it win).
  • Totals can be negative: don't initialise unreachable states with 0.

Reference solution

Python

from typing import List

def maximumAmount(coins: List[List[int]]) -> int:
    m, n = len(coins), len(coins[0])
    NEG = float('-inf')
    dp = [[[NEG] * 3 for _ in range(n)] for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                prev = [0, 0, 0]
            else:
                prev = [NEG] * 3
                for t in range(3):
                    if i > 0:
                        prev[t] = max(prev[t], dp[i - 1][j][t])
                    if j > 0:
                        prev[t] = max(prev[t], dp[i][j - 1][t])
            v = coins[i][j]
            for t in range(3):
                best = prev[t] + v
                if v < 0 and t > 0:
                    best = max(best, prev[t - 1])
                dp[i][j][t] = best
    return dp[m - 1][n - 1][2]

Java

public static int maximumAmount(int[][] coins) {
    int m = coins.length, n = coins[0].length;
    final int NEG = -1000000000;
    int[][][] dp = new int[m][n][3];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int[] prev = new int[3];
            if (!(i == 0 && j == 0)) {
                for (int t = 0; t < 3; t++) {
                    prev[t] = NEG;
                    if (i > 0) prev[t] = Math.max(prev[t], dp[i - 1][j][t]);
                    if (j > 0) prev[t] = Math.max(prev[t], dp[i][j - 1][t]);
                }
            }
            int v = coins[i][j];
            for (int t = 0; t < 3; t++) {
                int best = prev[t] + v;
                if (v < 0 && t > 0) best = Math.max(best, prev[t - 1]);
                dp[i][j][t] = best;
            }
        }
    }
    return dp[m - 1][n - 1][2];
}

C++

int maximumAmount(vector<vector<int>>& coins) {
    int m = coins.size(), n = coins[0].size();
    const int NEG = -1000000000;
    vector<vector<array<int, 3>>> dp(m, vector<array<int, 3>>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            array<int, 3> prev = {0, 0, 0};
            if (!(i == 0 && j == 0)) {
                for (int t = 0; t < 3; t++) {
                    prev[t] = NEG;
                    if (i > 0) prev[t] = max(prev[t], dp[i - 1][j][t]);
                    if (j > 0) prev[t] = max(prev[t], dp[i][j - 1][t]);
                }
            }
            int v = coins[i][j];
            for (int t = 0; t < 3; t++) {
                int best = prev[t] + v;
                if (v < 0 && t > 0) best = max(best, prev[t - 1]);
                dp[i][j][t] = best;
            }
        }
    }
    return dp[m - 1][n - 1][2];
}

JavaScript

var maximumAmount = function(coins) {
    var m = coins.length, n = coins[0].length;
    var NEG = -1000000000;
    var dp = [];
    for (var i = 0; i < m; i++) {
        var row = [];
        for (var j = 0; j < n; j++) row.push([NEG, NEG, NEG]);
        dp.push(row);
    }
    for (var r = 0; r < m; r++) {
        for (var c = 0; c < n; c++) {
            var prev = [NEG, NEG, NEG];
            if (r === 0 && c === 0) prev = [0, 0, 0];
            for (var t = 0; t < 3; t++) {
                if (r > 0 && dp[r - 1][c][t] > prev[t]) prev[t] = dp[r - 1][c][t];
                if (c > 0 && dp[r][c - 1][t] > prev[t]) prev[t] = dp[r][c - 1][t];
            }
            var v = coins[r][c];
            for (var u = 0; u < 3; u++) {
                var best = prev[u] + v;
                if (v < 0 && u > 0 && prev[u - 1] > best) best = prev[u - 1];
                dp[r][c][u] = best;
            }
        }
    }
    return dp[m - 1][n - 1][2];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming