0492HardArrayDynamic ProgrammingMatrixPrefix Sum

Terrace Soak Yield

Tracked in this browser only

Trains the technique from

LeetCode 3225Maximum Score From Grid Operations

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

Python

def best_soak_payout(grid: list[list[int]]) -> int:

Java

public long bestSoakPayout(int[][] grid)

The intended approach

Time O(n^3)Space O(n^2)

For a column at depth `d`, the plots that pay out are the rows from `d` up to one short of the deeper of its two neighbours, so the column's payout is a range sum over that column. Because crop values are never negative, taking the deeper neighbour is the same as taking whichever of the two sides gives more, which lets the sweep charge each column to exactly one of its neighbours. Sweep columns left to right, keeping for each depth of the current column two figures: the best total when that column's payout has already been charged to its left neighbour, and the best when it is still owed and will be charged to the neighbour on its right. Column prefix sums make each range sum constant time.

Pythonentry point: best_soak_payout

def best_soak_payout(grid):
    # Payouts are never negative, so a dry plot pays out exactly when its row lies
    # below the deeper of its two neighbouring depths, and "deeper of the two" can
    # be replaced by "whichever of the two is better", handled one column at a time.
    # Sweep columns left to right holding, for each depth of the current column,
    # the best total when that column's payout is already settled and the best when
    # it is still owed and will be settled by the column on its right.
    # time O(n^3), space O(n^2) for the column prefix sums
    n = len(grid)
    pre = []
    for c in range(n):
        column = [0] * (n + 1)
        for r in range(n):
            column[r + 1] = column[r] + grid[r][c]
        pre.append(column)
    settled = [0] * (n + 1)
    owed = [0] * (n + 1)
    for c in range(n - 1):
        next_settled = [0] * (n + 1)
        next_owed = [0] * (n + 1)
        for deep in range(n + 1):
            best_base = None
            best_settled = None
            for prev in range(n + 1):
                base = settled[prev]
                if deep > prev:
                    alt = owed[prev] + pre[c][deep] - pre[c][prev]
                else:
                    alt = owed[prev]
                if alt > base:
                    base = alt
                if best_base is None or base > best_base:
                    best_base = base
                gain = pre[c + 1][prev] - pre[c + 1][deep] if prev > deep else 0
                if best_settled is None or base + gain > best_settled:
                    best_settled = base + gain
            next_owed[deep] = best_base
            next_settled[deep] = best_settled
        settled, owed = next_settled, next_owed
    answer = 0
    for deep in range(n + 1):
        if settled[deep] > answer:
            answer = settled[deep]
        if owed[deep] > answer:
            answer = owed[deep]
    return answer

The obvious version

Walk every possible tuple of column depths with an explicit odometer, and for each tuple score the terrace by testing each plot against the two payout rules directly. Keeps the largest score. Exponential in the number of columns.

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_best_soak_payout(grid):
    n = len(grid)
    depths = [0] * n
    best = 0
    stack = [0]
    def payout():
        total = 0
        for r in range(n):
            for c in range(n):
                if r >= depths[c]:
                    left = c > 0 and r < depths[c - 1]
                    right = c + 1 < n and r < depths[c + 1]
                    if left or right:
                        total += grid[r][c]
        return total
    counters = [0] * n
    at = 0
    while at >= 0:
        if at == n:
            value = payout()
            if value > best:
                best = value
            at -= 1
            continue
        if counters[at] > n:
            counters[at] = 0
            at -= 1
            continue
        depths[at] = counters[at]
        counters[at] += 1
        at += 1
        if at < n:
            counters[at] = 0
    return best

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