Algorithm
Maximum Amount of Money Robot Can Earn
Solution
class Solution:
def maximumAmount(self, coins: List[List[int]]) -> int:
m, n = len(coins), len(coins[0])
dp = [[-math.inf] * 3 for _ in range(n + 1)]
dp[1][0] = 0
dp[1][1] = 0
dp[1][2] = 0
for i in range(m):
next_dp = [[-math.inf] * 3 for _ in range(n + 1)]
for j in range(n):
for k in range(3):
# Base transition (no neutralization here)
best_prev = max(dp[j + 1][k], next_dp[j][k])
if best_prev != -math.inf:
next_dp[j + 1][k] = max(next_dp[j + 1][k], best_prev + coins[i][j])
# Transition with neutralization
if k > 0:
best_prev_power = max(dp[j + 1][k - 1], next_dp[j][k - 1])
if best_prev_power != -math.inf and coins[i][j] < 0:
next_dp[j + 1][k] = max(next_dp[j + 1][k], best_prev_power)
# Special setup for first cell handling on first row
if i == 0:
next_dp[0] = [-math.inf] * 3
dp = next_dp
return max(dp[n])Video GuideLeetcode Daily
Time Complexity
O(mn)
Space Complexity
O(n)
