Show problems as
Classic problem #3418MediumArrayDynamic ProgrammingMatrix

Maximum Amount of Money Robot Can Earn

Real-world version: Best Haul Across the Yard With Two Waivers
Tracked in this browser only
Read Maximum Amount of Money Robot Can Earn on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A yard is laid out as coins. A cart starts at the top-left cell and finishes at the bottom-right, moving only one cell right or one cell down at a time.

Entering a cell adds its value to the haul, and a negative value is a toll. The cart carries two waivers; each may be spent on one cell it enters whose value is negative, and that cell then counts as nothing at all. Waivers may be left unused and cannot be spent on a cell whose value is not negative.

Return the largest haul the cart can finish with.

Examples

Example 1

Input
coins = [[7, -13, 4], [-9, 6, -21], [3, -5, 8]]
Output
21

Going right, right, down, down waives the tolls of 13 and 21 and collects 7, 4 and 8, coming to 19. No other route with two waivers does better.

Example 2

Input
coins = [[-1, -2], [-3, -4]]
Output
-1

Every cell is a toll and every route enters three cells, so two of them are waived and the cheapest remaining toll is paid. Going down then right leaves the toll of 1 as the one to pay after waiving 3 and 4.

Example 3

Input
coins = [[5]]
Output
5

The cart starts where it finishes, and the single cell is not a toll, so neither waiver is of any use.

Constraints

  • 1 <= coins.length <= 500
  • 1 <= coins[i].length <= 500
  • Every row of coins has the same length
  • -1000 <= coins[i][j] <= 1000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def maximum_amount(coins: list[list[int]]) -> int:
Java
public int maximumAmount(int[][] coins)

More on the same topics