Show problems as
Classic problem #3225HardArrayDynamic ProgrammingMatrixPrefix Sum

Maximum Score From Grid Operations

Real-world version: Terrace Soak Yield
Tracked in this browser only
Read Maximum Score From Grid Operations on LeetCode(opens in a new tab)

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

A hillside terrace is laid out as an n by n block of plots. grid[r][c] is the crop value of the plot in row r and column c, with row 0 along the top edge.

Before the season starts you fix, for each column c on its own, a soak depth between 0 and n. Water poured into a column soaks the top plots of that column, so a depth of d leaves rows 0 through d - 1 of that column soaked and every row from d downwards dry. A depth of 0 leaves the whole column dry and a depth of n soaks all of it.

At harvest a plot pays out its crop value only when both of these hold:

  • the plot itself is dry, and
  • the plot immediately to its left or the plot immediately to its right, in the same row, is soaked.

A soaked plot pays out nothing, and neither does a dry plot whose horizontal neighbours are all dry. Plots in the leftmost and rightmost columns have a single horizontal neighbour.

Return the largest total payout you can arrange by choosing the depths.

Examples

Example 1

Input
grid = [[5, 0], [0, 0]]
Output
5

Soaking the right column to depth 1 and leaving the left column dry makes the plot worth 5 a dry plot with a soaked neighbour, so it pays out.

Example 2

Input
grid = [[0, 9, 0], [0, 0, 0], [0, 9, 0]]
Output
18

Soaking the outer two columns all the way down leaves the middle column dry with soaked plots on both sides in every row, so both plots worth 9 pay out.

Example 3

Input
grid = [[41]]
Output
0

A single column has no horizontal neighbour at all, so whatever depth is chosen nothing pays out.

Constraints

  • 1 <= n == grid.length <= 100
  • n == grid[i].length
  • 0 <= grid[i][j] <= 10^9

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 best_soak_payout(grid: list[list[int]]) -> int:
Java
public long bestSoakPayout(int[][] grid)

More on the same topics