396. Maximum Score From Grid Operations

An operation paints column j black from row 0 down to some row h_j (or leaves it white if h_j = -1). The whole solution is determined by (h_0, h_1, …, h_{n-1}). Try every vector and keep the maximum score.

Approach

1. Recursively pick h_j ∈ {-1, 0, 1, …, n - 1} for each column.
2. After all columns are decided, scan the grid: a cell (i, j) is white iff i > h_j; it scores grid[i][j] if a horizontally adjacent cell ((i, j - 1) or (i, j + 1)) is black.
3. Track the maximum.

Complexity

• Time: O((n + 1)^n · n²) — only feasible for tiny n.
• Space: O(n²).

class Solution {
    private int best;

    public long maximumScore(int[][] grid) {
        int n = grid.length;
        best = 0;
        int[] heights = new int[n];
        go(grid, n, 0, heights);
        return best;
    }

    private void go(int[][] grid, int n, int j, int[] heights) {
        if (j == n) {
            evaluate(grid, n, heights);
            return;
        }
        for (int h = -1; h < n; h++) {
            heights[j] = h;
            go(grid, n, j + 1, heights);
        }
    }

    private void evaluate(int[][] grid, int n, int[] heights) {
        int score = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i > heights[j]) {
                    boolean left = j > 0 && i <= heights[j - 1];
                    boolean right = j < n - 1 && i <= heights[j + 1];
                    if (left || right) {
                        score += grid[i][j];
                    }
                }
            }
        }
        if (score > best) best = score;
    }
}

Each column independently chooses a black height — how many rows from the top to paint black. Scoring is local: a white cell in column j only earns points if its left or right neighbour in the same row is black. So once you fix two adjacent columns' heights, the contribution between them is determined. That structure begs for a DP over columns.

Reframing the problem

The operation "select (i, j) and color rows 0..i of column j black" is equivalent to picking, for each column, a black-region height h_j ∈ {0, 1, …, n} (where h_j = 0 means no rows are black). All operations on column j collapse into one final height because later operations on the same column can only extend downward — the final state is "the top h_j rows of column j are black".

So a solution is a vector (h_0, h_1, …, h_{n-1}). We want to maximise:

score = Σ over white cells (i, j) such that some horizontal neighbour is black
       = Σ_{j} Σ_{i ≥ h_j and (i < h_{j-1} or i < h_{j+1})} grid[i][j]

How adjacent columns interact

Look at two adjacent columns j - 1 and j with heights p and h:

• Column j rows h..min(p, n) - 1 are white in j and black in j - 1, so they score from the left neighbour. Contribution: pre[j][p] - pre[j][h] if p > h, else 0. (Here pre[j][r] = grid[0][j] + grid[1][j] + … + grid[r - 1][j].)
• Column j - 1 rows p..min(h, n) - 1 are white in j - 1 and black in j, so they score from the right neighbour. Contribution: pre[j - 1][h] - pre[j - 1][p] if h > p else 0.

Note: at most one of those two cases is non-zero (h > p or p > h, never both).

DP state

Define dp[j][h] = best total score considering columns 0..j where column j has height h. But there's a twist: the bonus that column j - 1 earns from column j's black cells depends on h of column j, which we'd want to charge when we decide column j's height. To avoid double-counting, we extend the state with m = the maximum of prev_h and curr_h, marking how far down column j-1's black extended or how far down column j's black extends. The transition becomes:

dp[j][curr_h][new_m] = max over prev_h of
    dp[j-1][prev_h][old_m]
  + bonus_from_j_to_jminus1(prev_h, curr_h)
  + bonus_from_jminus1_to_j(prev_h, curr_h)

The m-dimension makes the transition cleanly O(n) per (j, curr_h) after a prefix/suffix-max optimization.

Complexity-saving trick

Naively, dp[j][h] has O(n²) states and each transition scans O(n) predecessors → O(n³) total. The pmax and smax arrays in the code below precompute max over m of dp[prev_h][m] (with adjustments) so each (j, curr_h) transition is O(1) after an O(n) preprocessing step per prev_h. Total: O(n · n · n) = O(n³).

Steps

1. Prefix sums per column: pre[j][r] = sum of grid[0..r-1][j].
2. Initialise dp[h][h] = 0 for all h (column 0 with height h and m = h has score 0).
3. For each column j from 1 to n - 1:
   • For each candidate prev_h, build the pmax (prefix-max with adjustment) and smax (suffix-max) helpers over dp[prev_h][·].
   • For each curr_h, compute the new entry ndp[curr_h][new_m] using the helpers + the column-j-only bonus pre[j][prev_h] - pre[j][curr_h] when prev_h > curr_h.
4. Answer: the maximum entry in dp[h][m] after the last column.

Walk-through

Take the small case grid = [[1,2,3],[4,5,6],[7,8,9]], n = 3. Expected answer: 30.

The optimal heights are (h_0, h_1, h_2) = (3, 0, 3) — paint columns 0 and 2 fully black, leave column 1 fully white. Then every cell of column 1 is white with both horizontal neighbours black, scoring 2 + 5 + 8 = 15 twice (once for left-adjacency, once for right-adjacency)? No — the score counts each white cell once if any horizontal neighbour is black. So column 1 contributes 2 + 5 + 8 = 15. Plus columns 0 and 2 are entirely black, scoring 0. Total 15 — but the expected output is 30.

Reconsider: when both neighbours are black, the white cell still counts as 1 toward the score (it has a black horizontal neighbour). So column 1 alone gives 15. To get 30 we'd need columns 0 and 2 to contribute too. Let's try (0, 3, 0): column 1 fully black, columns 0 and 2 fully white. Column 0 gets points from column 1 being black: 1 + 4 + 7 = 12. Column 2: 3 + 6 + 9 = 18. Column 1 black so no points from itself. Total: 30. ✓

Edge cases

• n == 1: there's only one column, no horizontal neighbours, so the answer is 0.
• All zeros: answer is 0.
• Painting nothing black: answer is 0 (no white cell has a black neighbour).

Complexity

• Time: O(n³).
• Space: O(n²) — the DP table.

Why this problem is hard

The branching O((n+1)^n) brute force is exponential. To reach O(n³) you have to (a) realise the choice per column is just a height, (b) design a DP state that tracks enough info to compute inter-column bonuses without double-counting, and (c) optimise the transition with prefix/suffix maxima. Each step is a non-trivial leap.