Maximum Score From Grid Operations

Problem

We are given an n x n grid. In one operation, we choose a cell (i, j) and color every cell in column j from row 0 to row i black.

After all operations, a white cell contributes to the score if it has a horizontally adjacent black cell. We need the maximum score possible.

The important observation is that each column can only look like this:

black
black
black
white
white

So instead of thinking about every cell independently, we only need to know the black height of every column.

Key Idea

Let h[j] be the number of black cells in column j.

If h[j] = 3, then rows 0, 1, 2 are black and rows 3...n-1 are white.

Now compare two adjacent columns:

• If the left column is taller, then some white cells in the right column see black on the left.
• If the right column is taller, then some white cells in the left column see black on the right.

That means the score created around a column depends only on nearby column heights. This is exactly the kind of structure where dynamic programming works.

Prefix Sums

We need fast column range sums.

Define:

colSum[c][r] = sum of grid[0][c] + grid[1][c] + ... + grid[r - 1][c]

Then the sum from row l to row r - 1 in column c is:

colSum[c][r] - colSum[c][l]

This lets every DP transition ask for a vertical strip in O(1).

DP State

Use:

dp[i][currH][prevH]

as the maximum score after processing up to column i, where:

• column i has currH black cells
• column i - 1 has prevH black cells

Why keep two heights?

Because when we move from column i - 1 to column i, we may still need to know how column i - 2 interacted with column i - 1. The transition is really about three consecutive columns:

i - 2, i - 1, i

The naive transition would also enumerate the height k of column i - 2, which gives O(n^4).

We optimize that enumeration using prefix and suffix maximum arrays.

Transition

There are two cases.

Case 1: currH <= prevH

Column i - 1 has at least as many black cells as column i.

So rows [currH, prevH) in column i are white cells that see black on the left.

Extra score:

colSum[i][prevH] - colSum[i][currH]

The previous height k does not change this extra score, so we only need the best old DP value:

dp[i][currH][prevH] =
  max(dp[i - 1][prevH][k]) + colSum[i][prevH] - colSum[i][currH]

That maximum is stored in prevSuffixMax[prevH][0].

Case 2: currH > prevH

Now column i is taller than column i - 1.

Rows [prevH, currH) in column i - 1 may become white cells that see black on the right.

But we must avoid double counting cells in column i - 1 that may already have been counted because of column i - 2.

This is where the optimized helper arrays matter:

• prevMax handles previous heights k <= currH, after subtracting the part that would be double counted.
• prevSuffixMax handles previous heights k > currH, where no new contribution is needed.

So:

extra = colSum[i - 1][currH] - colSum[i - 1][prevH]

dp[i][currH][prevH] =
  max(
    prevSuffixMax[prevH][currH],
    prevMax[prevH][currH] + extra
  )

The code looks a little dense, but the idea is simple: precompute the best value for all possible k ranges so every state transitions in O(1).

Why The Last Column Is Special

The last column has no column to its right.

So after deciding everything else, the last column only needs to be one of two useful extremes:

• 0 black cells
• n black cells

Anything in between cannot help a future column, because there is no future column.

That is why the final answer checks:

dp[n - 1][0][k]
dp[n - 1][n][k]

for every previous height k.

class Solution {
    public long maximumScore(int[][] grid) {
        int n = grid.length;
        if (n == 1) {
            return 0;
        }

        long[][][] dp = new long[n][n + 1][n + 1];
        long[][] prevMax = new long[n + 1][n + 1];
        long[][] prevSuffixMax = new long[n + 1][n + 1];
        long[][] colSum = new long[n][n + 1];

        for (int c = 0; c < n; c++) {
            for (int r = 1; r <= n; r++) {
                colSum[c][r] = colSum[c][r - 1] + grid[r - 1][c];
            }
        }

        for (int i = 1; i < n; i++) {
            for (int currH = 0; currH <= n; currH++) {
                for (int prevH = 0; prevH <= n; prevH++) {
                    if (currH <= prevH) {
                        long extraScore = colSum[i][prevH] - colSum[i][currH];
                        dp[i][currH][prevH] = prevSuffixMax[prevH][0] + extraScore;
                    } else {
                        long extraScore = colSum[i - 1][currH] - colSum[i - 1][prevH];
                        dp[i][currH][prevH] = Math.max(
                            prevSuffixMax[prevH][currH],
                            prevMax[prevH][currH] + extraScore
                        );
                    }
                }
            }

            for (int currH = 0; currH <= n; currH++) {
                prevMax[currH][0] = dp[i][currH][0];
                for (int prevH = 1; prevH <= n; prevH++) {
                    long penalty = prevH > currH
                        ? colSum[i][prevH] - colSum[i][currH]
                        : 0;
                    prevMax[currH][prevH] = Math.max(
                        prevMax[currH][prevH - 1],
                        dp[i][currH][prevH] - penalty
                    );
                }

                prevSuffixMax[currH][n] = dp[i][currH][n];
                for (int prevH = n - 1; prevH >= 0; prevH--) {
                    prevSuffixMax[currH][prevH] = Math.max(
                        prevSuffixMax[currH][prevH + 1],
                        dp[i][currH][prevH]
                    );
                }
            }
        }

        long answer = 0;
        for (int k = 0; k <= n; k++) {
            answer = Math.max(answer, Math.max(dp[n - 1][0][k], dp[n - 1][n][k]));
        }

        return answer;
    }
}

Complexity

Let n be the grid size.

• Time complexity: O(n^3)
• Space complexity: O(n^3)

The DP has n * (n + 1) * (n + 1) states, and each state is computed in O(1) after the helper maximum arrays are prepared.

The space can be reduced to O(n^2) with rolling arrays, but the full DP version is easier to read and reason about.

Final Takeaway

The trick is to stop seeing the grid as n^2 independent cells.

Each column is completely described by one number: its black height.

Once we model the grid as a sequence of column heights, the problem becomes a dynamic programming problem over adjacent columns. The hard part is only optimizing the third height enumeration from O(n) to O(1) with prefix and suffix maximums.