m × n board grid from the top-left cell to the bottom-right one, each step moving either right or down. The start and finish cells count as part of the route.
Each cell holds a number. If it is non-negative, the courier picks up that many coins. If it is negative, a robber waits there and takes away its absolute value.
The courier carries two shields: in up to two cells of the route a robbery can be cancelled, and such a cell takes nothing. The courier's balance is allowed to go negative.
Return the largest amount the courier can finish with.grid=[[3, -5, 2], [-4, -6, 1], [2, -1, 4]] → 10
The route 3 → -5 → 2 → 1 → 4 (right, right, down, down) with a shield on the -5 cell gives 3 + 2 + 1 + 4 = 10.
grid=[[1, -2, 3, -4, 5]] → 9
There is only one path. Both shields go to the negative cells: 1 + 3 + 5 = 9.
grid=[[-3]] → 0
A shield cancels the loss in the only cell, so the total is 0.
grid=[[3, -5, 2], [-4, -6, 1], [2, -1, 4]]
10
Run checks the first 3 tests in your browser. Submit checks all 75 tests on the server, hidden ones included.