3225. Maximum Score From Grid Operations

Array
Dynamic Programming
Matrix
Prefix Sum

TIME

O(n^3)

SPACE

O(n^2)

Intuition

For each column j, choose a "height" h[j] = number of black cells (0 to n). A white cell (i,j) scores if it's white (i >= h[j]) AND has adjacent black cell (i < h[j-1] OR i < h[j+1]).

Score from column j = sum of grid[i][j] for h[j] <= i < max(h[j-1], h[j+1]).

Solution

DP State

dp[a][b] = max score where h[prev_col] = a, h[curr_col] = b, with all previous columns fully scored.

Transition

When moving from column j to j+1:

Column j's contribution = psum[j][max(a, c)] - psum[j][b] if max(a, c) > b

Where a = h[j-1], b = h[j], c = h[j+1].

Optimization

Use prefix/suffix max arrays to reduce from O(n^4) to O(n^3):

suffix[a][b] = max over k >= a of (dp[k][b] + psum[j][k])
prefix[a][b] = max over k < a of dp[k][b]

For c > b: contribution comes from either a >= c or a < c case. For c <= b: contribution only from a > b.

Complexity

Time: O(n³)
Space: O(n²)

Edge Cases

Single column → score is 0
All zeros → score is 0
Large values requiring long long in Java

Code

from typing import List


class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        """
        3225. Maximum Score From Grid Operations
        Time: O(n^3)
        Space: O(n^2)
        """
        n = len(grid)

        # Precompute prefix sums for each column
        psum = [[0] * (n + 1) for _ in range(n)]
        for j in range(n):
            for i in range(n):
                psum[j][i + 1] = psum[j][i] + grid[i][j]

        NEG_INF = float("-inf")

        # dp[a][b] = max score, h[prev_col] = a, h[curr_col] = b
        dp = [[NEG_INF] * (n + 1) for _ in range(n + 1)]
        for b in range(n + 1):
            dp[0][b] = 0  # h[-1] = 0

        for j in range(n - 1):
            # suffix[a][b] = max over k >= a of (dp[k][b] + psum[j][k])
            suffix = [[NEG_INF] * (n + 1) for _ in range(n + 2)]
            # prefix[a][b] = max over k < a of dp[k][b]
            prefix = [[NEG_INF] * (n + 1) for _ in range(n + 2)]

            for b in range(n + 1):
                for a in range(n, -1, -1):
                    suffix[a][b] = max(dp[a][b] + psum[j][a], suffix[a + 1][b])

                for a in range(1, n + 2):
                    prev_dp = dp[a - 1][b] if a - 1 <= n else NEG_INF
                    prefix[a][b] = max(prefix[a - 1][b], prev_dp)

            new_dp = [[NEG_INF] * (n + 1) for _ in range(n + 1)]

            for b in range(n + 1):
                # Case: c <= b (contribution only from a > b)
                val = max(suffix[b + 1][b] - psum[j][b], prefix[b + 1][b])
                for c in range(b + 1):
                    new_dp[b][c] = val

                # Case: c > b
                for c in range(b + 1, n + 1):
                    val = max(suffix[c][b], prefix[c][b] + psum[j][c]) - psum[j][b]
                    new_dp[b][c] = val

            dp = new_dp

        # Final: add column n-1's contribution (h[n] = 0)
        ans = 0
        for a in range(n + 1):
            for b in range(n + 1):
                if dp[a][b] == NEG_INF:
                    continue
                contrib = psum[n - 1][a] - psum[n - 1][b] if a > b else 0
                ans = max(ans, dp[a][b] + contrib)

        return ans

/**
 * 3225. Maximum Score From Grid Operations
 * Time: O(n^3)
 * Space: O(n^2)
 */
class Solution {
    public long maximumScore(int[][] grid) {
        int n = grid.length;

        // Precompute prefix sums for each column
        long[][] psum = new long[n][n + 1];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                psum[j][i + 1] = psum[j][i] + grid[i][j];
            }
        }

        long NEG_INF = Long.MIN_VALUE / 2;

        // dp[a][b] = max score, h[prev_col] = a, h[curr_col] = b
        long[][] dp = new long[n + 1][n + 1];
        for (int a = 0; a <= n; a++) {
            for (int b = 0; b <= n; b++) {
                dp[a][b] = (a == 0) ? 0 : NEG_INF;
            }
        }

        for (int j = 0; j < n - 1; j++) {
            long[][] suffix = new long[n + 2][n + 1];
            long[][] prefix = new long[n + 2][n + 1];

            for (int b = 0; b <= n; b++) {
                suffix[n + 1][b] = NEG_INF;
                for (int a = n; a >= 0; a--) {
                    suffix[a][b] = Math.max(dp[a][b] + psum[j][a], suffix[a + 1][b]);
                }

                prefix[0][b] = NEG_INF;
                for (int a = 1; a <= n + 1; a++) {
                    long prevDp = (a - 1 <= n) ? dp[a - 1][b] : NEG_INF;
                    prefix[a][b] = Math.max(prefix[a - 1][b], prevDp);
                }
            }

            long[][] newDp = new long[n + 1][n + 1];
            for (int i = 0; i <= n; i++) {
                for (int k = 0; k <= n; k++) {
                    newDp[i][k] = NEG_INF;
                }
            }

            for (int b = 0; b <= n; b++) {
                // Case: c <= b
                long val = Math.max(suffix[b + 1][b] - psum[j][b], prefix[b + 1][b]);
                for (int c = 0; c <= b; c++) {
                    newDp[b][c] = val;
                }

                // Case: c > b
                for (int c = b + 1; c <= n; c++) {
                    val = Math.max(suffix[c][b], prefix[c][b] + psum[j][c]) - psum[j][b];
                    newDp[b][c] = val;
                }
            }

            dp = newDp;
        }

        // Final: add column n-1's contribution
        long ans = 0;
        for (int a = 0; a <= n; a++) {
            for (int b = 0; b <= n; b++) {
                if (dp[a][b] == NEG_INF) continue;
                long contrib = (a > b) ? psum[n - 1][a] - psum[n - 1][b] : 0;
                ans = Math.max(ans, dp[a][b] + contrib);
            }
        }

        return ans;
    }
}