0916MediumArrayDynamic ProgrammingMatrix

Best Haul Across the Yard With Two Waivers

Tracked in this browser only

Trains the technique from

LeetCode 3418Maximum Amount of Money Robot Can Earn

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def maximum_amount(coins: list[list[int]]) -> int:

Java

public int maximumAmount(int[][] coins)

The intended approach

Time O(m * n) for an m by n yard, with three figures per cell.Space O(m * n), or O(n) keeping only the previous row.

The cart only moves right and down, so a cell can only be reached from the cell above it or the one to its left, which makes the best haul to a cell settled once its two neighbours are. The waivers add one more thing to remember: how many are still in hand. So carry three figures per cell, one for each of two, one and no waivers left. Arriving at a cell with a given number of waivers left, the cart either pays the cell's value or, when the value is negative and it still has a waiver, spends one and pays nothing, which draws on the figure for one more waiver from the neighbour. Taking the better of the two at each step and the best of the three at the finish gives the answer. Unreachable states have to be kept apart from reachable ones, since a haul may legitimately be negative.

Pythonentry point: maximum_amount

def maximum_amount(coins):
    m = len(coins)
    n = len(coins[0])
    NONE = None
    best = [[[NONE, NONE, NONE] for _ in range(n)] for _ in range(m)]

    def better(a, b):
        if a is None:
            return b
        if b is None:
            return a
        return a if a > b else b

    for r in range(m):
        for c in range(n):
            value = coins[r][c]
            for left in range(3):
                # the best haul arriving at this cell, before paying for it
                arriving = None
                if r == 0 and c == 0:
                    arriving = 0 if left == 2 else None
                else:
                    if r > 0:
                        arriving = better(arriving, best[r - 1][c][left])
                    if c > 0:
                        arriving = better(arriving, best[r][c - 1][left])
                    # or arriving with one more waiver and spending it here
                    if value < 0 and left < 2:
                        spent = None
                        if r > 0:
                            spent = better(spent, best[r - 1][c][left + 1])
                        if c > 0:
                            spent = better(spent, best[r][c - 1][left + 1])
                        if spent is not None:
                            best[r][c][left] = better(best[r][c][left], spent)
                if arriving is not None:
                    best[r][c][left] = better(best[r][c][left], arriving + value)
                if r == 0 and c == 0 and value < 0 and left < 2:
                    # the starting cell may itself be waived
                    if left == 1:
                        best[r][c][left] = better(best[r][c][left], 0)
    answer = None
    for left in range(3):
        answer = better(answer, best[m - 1][n - 1][left])
    return answer

The obvious version

Walk out every route the cart could take and, for each one, try every choice of which of its negative cells to waive, keeping the best haul found. Exponential in the yard's size and it remembers nothing between routes.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_maximum_amount(coins):
    m = len(coins)
    n = len(coins[0])
    best = [None]

    def walk(r, c, picked):
        picked.append(coins[r][c])
        if r == m - 1 and c == n - 1:
            negatives = sorted(v for v in picked if v < 0)
            total = 0
            for v in picked:
                total += v
            # waiving a cell adds back its toll; take the two worst tolls on the route
            saved = 0
            for i in range(min(2, len(negatives))):
                saved -= negatives[i]
            if best[0] is None or total + saved > best[0]:
                best[0] = total + saved
        else:
            if r + 1 < m:
                walk(r + 1, c, picked)
            if c + 1 < n:
                walk(r, c + 1, picked)
        picked.pop()

    walk(0, 0, [])
    return best[0]

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in