Maximum score from grid operations

Array Dynamic Programming Matrix Prefix Sum

27.0% acceptance

Feb 25, 2026

You are given a 2D matrix grid of size n x n. Initially, all cells of the grid are colored white. In one operation, you can select any cell of indices (i, j), and color black all the cells of the jth column starting from the top row down to the ith row. The grid score is the sum of all grid[i][j] such that cell (i, j) is white and it has a horizontally adjacent black cell. Return the maximum score that can be achieved after some number of operations.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_score(grid: Vec<Vec<i32>>) -> i64 {
    let n = grid.len();
    // ps[c][r] = prefix sum of column c for rows 0..r
    let mut ps = vec![vec![0i64; n + 1]; n];
    for c in 0..n {
      for r in 0..n {
        ps[c][r + 1] = ps[c][r] + grid[r][c] as i64;
      }
    }
    let col_sum = |c: usize, from: usize, to: usize| -> i64 {
      if to <= from { 0 } else { ps[c][to] - ps[c][from] }
    };

    const NEG_INF: i64 = i64::MIN / 2;
    // dp[h_prev][h_curr]: max score after processing columns 0..=j
    // h_prev = height of column j-1, h_curr = height of column j (both in 0..=n)
    // h_prev = 0 acts as sentinel: no left neighbour (initial state for column 0)
    let mut dp = vec![vec![NEG_INF; n + 1]; n + 1];
    for h0 in 0..=n {
      dp[0][h0] = 0;
    }

    // Transition: for each column j, compute contribution of column j given its
    // three-column neighbourhood (h_prev, h_curr, h_next).
    //
    // contrib(h_prev, h_curr, h_next) = col_sum(j, h_curr, max(h_prev, h_next))
    //
    // Split into two cases to avoid O(n^3) inner loop:
    //   Case A  h_prev <= h_next → contrib = col_sum(j, h_curr, h_next)
    //     new_dp[h_curr][h_next] = prefix_max[h_curr][h_next] + col_sum(j, h_curr, h_next)
    //     where prefix_max[h_curr][k] = max dp[h_prev][h_curr] for h_prev in 0..=k
    //
    //   Case B  h_prev >  h_next → contrib = col_sum(j, h_curr, h_prev)
    //     new_dp[h_curr][h_next] = suffix_val[h_curr][h_next+1]
    //     where suffix_val[h_curr][k] = max (dp[h_prev][h_curr] + col_sum(j, h_curr, h_prev))
    //                                       for h_prev in k..=n
    //
    // Overall complexity: O(n^3).
    for j in 0..n.saturating_sub(1) {
      // Precompute prefix_max and suffix_val per h_curr  (both O(n^2) total)
      let mut pm  = vec![vec![NEG_INF; n + 1]; n + 1]; // pm[h_curr][k]
      let mut sv  = vec![vec![NEG_INF; n + 2]; n + 1]; // sv[h_curr][k], extra slot at n+1

      for h_curr in 0..=n {
        let mut mx = NEG_INF;
        for h_prev in 0..=n {
          let v = dp[h_prev][h_curr];
          if v != NEG_INF { mx = mx.max(v); }
          pm[h_curr][h_prev] = mx;
        }
        sv[h_curr][n + 1] = NEG_INF;
        for h_prev in (0..=n).rev() {
          let v = if dp[h_prev][h_curr] != NEG_INF {
            dp[h_prev][h_curr] + col_sum(j, h_curr, h_prev)
          } else { NEG_INF };
          sv[h_curr][h_prev] = v.max(sv[h_curr][h_prev + 1]);
        }
      }

      let mut new_dp = vec![vec![NEG_INF; n + 1]; n + 1];
      for h_curr in 0..=n {
        for h_next in 0..=n {
          let case_a = if pm[h_curr][h_next] != NEG_INF {
            pm[h_curr][h_next] + col_sum(j, h_curr, h_next)
          } else { NEG_INF };
          let case_b = sv[h_curr][h_next + 1];
          new_dp[h_curr][h_next] = case_a.max(case_b);
        }
      }
      dp = new_dp;
    }

    // Final: last column (no right neighbour); only left adjacency contributes.
    let j = n - 1;
    let mut ans = 0i64;
    for h_prev in 0..=n {
      for h_curr in 0..=n {
        if dp[h_prev][h_curr] != NEG_INF {
          let total = dp[h_prev][h_curr] + col_sum(j, h_curr, h_prev);
          if total > ans { ans = total; }
        }
      }
    }
    ans
  }
}