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.lengthn == coins[i].length1 <= m, n <= 500-1000 <= coins[i][j] <= 1000
Hints for Maximum Amount of Money Robot Can Earn
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]).Hint 2
The only extra information a path carries is how many neutralizations it has used — 0, 1 or 2.
Hint 3
dp[i][j][t]= best total reaching(i, j)using at mosttneutralizations: either take the cell (best[t] + coins[i][j]) or, for a robber andt > 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
- Let
dp[i][j][t]be the best total on arrival at(i, j)having neutralized at mosttrobbers (tin 0..2). - For each cell, let
prev[t]be the better of the cell above and the cell to the left (or 0 for everytat the start cell). - Set
dp[i][j][t] = prev[t] + coins[i][j]; ifcoins[i][j] < 0andt > 0, also tryprev[t - 1](neutralize this cell). - 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