Maximum Score From Grid Operations
Source: leetcode
Difficulty: Hard
Tags: array, dynamic-programming, matrix, prefix-sum

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.


 


**Example 1:**



**Input:** grid \= \[\[0,0,0,0,0],\[0,0,3,0,0],\[0,1,0,0,0],\[5,0,0,3,0],\[0,0,0,0,2]]


**Output:** 11


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/05/11/one.png)
In the first operation, we color all cells in column 1 down to row 3, and in the second operation, we color all cells in column 4 down to the last row. The score of the resulting grid is `grid[3][0] + grid[1][2] + grid[3][3]` which is equal to 11\.



**Example 2:**



**Input:** grid \= \[\[10,9,0,0,15],\[7,1,0,8,0],\[5,20,0,11,0],\[0,0,0,1,2],\[8,12,1,10,3]]


**Output:** 94


**Explanation:**


![](https://assets.leetcode.com/uploads/2024/05/11/two-1.png)
We perform operations on 1, 2, and 3 down to rows 1, 4, and 0, respectively. The score of the resulting grid is `grid[0][0] + grid[1][0] + grid[2][1] + grid[4][1] + grid[1][3] + grid[2][3] + grid[3][3] + grid[4][3] + grid[0][4]` which is equal to 94\.



 


**Constraints:**


- `1 <= n == grid.length <= 100`
- `n == grid[i].length`
- `0 <= grid[i][j] <= 109`




C++ solution:
#define ll long long

class Solution {
public:
    ll maximumScore(vector<vector<int>>& grid) {
        int n = grid.size(), i, j, k;
        if (n == 1) return 0;
        // each black column can only affect column before and after it
        ll colpr[n + 1][n + 1];
        memset(colpr, 0, sizeof(colpr));
        for (i = 0; i < n; i++) grid[i].push_back(0);
        for (j = 0; j <= n; j++) {
            for (i = 0; i < n; i++) colpr[i + 1][j] = colpr[i][j] + grid[i][j];
        }
        if (n == 2) return max(colpr[n][0], colpr[n][1]);
        ll best = 0;
        ll dpup[n][n], dpdown[n][n], rmax[n], onesuf[n], twosuf[n], a, one, two;
        int onep, twop;
        memset(dpup, 0, sizeof(dpup));
        memset(dpdown, 0, sizeof(dpdown));
        memset(rmax, 0, sizeof(rmax));
        memset(onesuf, 0, sizeof(onesuf));
        memset(twosuf, 0, sizeof(twosuf));
        // col 0
        for (i = 0; i < n; i++) dpup[i][0] = colpr[i + 1][1];
        
        // col 1
        for (i = 0; i < n; i++) dpup[i][1] = colpr[i + 1][0] + colpr[i + 1][2];
        for (i = 0; i < n - 1; i++) dpdown[i][1] = dpup[n - 1][0] + colpr[i + 1][2] - colpr[i + 1][1];

        // col 2
        for (i = 0; i < n; i++) {
            dpup[i][2] = colpr[i + 1][1] + colpr[i + 1][3];
            best = max(dpup[n - 1][0] - colpr[i + 1][1], 0ll);
            for (k = 0; k <= i; k++) best = max(best, dpup[k][1] - colpr[k + 1][1] - colpr[k + 1][2]);
            dpup[i][2] += best;
        }
        for (i = 0; i < n - 1; i++) {
            dpdown[i][2] = colpr[i + 1][3];
            best = 0;
            for (k = n - 1; k >= i; k--) best = max(best, dpdown[k][1] - colpr[i + 1][2]);
            for (k = n - 1; k >= i; k--) best = max(best, dpup[k][1] - colpr[i + 1][2]);
            dpdown[i][2] += best;
        }

        // col 3+
        for (j = 3; j < n; j++) {
            a = 0;
            for (k = 0; k < n; ++k) {
                rmax[k] = max(rmax[k], dpup[k][j - 3]);
                a = max(a, rmax[k]);
            }
            for (k = 0; k < n; ++k) {
                rmax[k] = max(rmax[k], dpdown[k][j - 3]);
                a = max(a, rmax[k]);
            }
            one = 0, two = 0;
            onep, twop;
            for (k = n - 1; k >= 0; --k) {
                if (dpup[k][j - 2] > one) {
                    one = dpup[k][j - 2];
                    onep = k;
                }
                onesuf[k] = dpup[k][j - 2];
                if (k != n - 1) onesuf[k] = max(onesuf[k], onesuf[k + 1]);
            }
            for (k = n - 1; k >= 0; --k) {
                if (dpdown[k][j - 2] > two) {
                    two = dpdown[k][j - 2];
                    twop = k;
                }
                twosuf[k] = dpdown[k][j - 2];
                if (k != n - 1) twosuf[k] = max(twosuf[k], twosuf[k + 1]);
            }

            for (i = 0; i < n; ++i) {
                dpup[i][j] = colpr[i + 1][j - 1] + colpr[i + 1][j + 1];
                best = 0;
                a = max(a, dpup[i][j - 1] - colpr[i + 1][j - 1] - colpr[i + 1][j]);
                if (onesuf[i] - colpr[i + 1][j - 1] > one - colpr[min(onep, i) + 1][j - 1]) {
                    one = onesuf[i];
                    onep = i;
                }
                if (twosuf[i] - colpr[i + 1][j - 1] > two - colpr[min(twop, i) + 1][j - 1]) {
                    two = twosuf[i];
                    twop = i;
                }
                dpup[i][j] += max(best, max(a, max(one - colpr[i + 1][j - 1], two - colpr[i + 1][j - 1])));
            }
            best = 0;
            for (i = n - 1; i >= 0; --i) {
                dpdown[i][j] = colpr[i + 1][j + 1];
                best = max(best, max(dpup[i][j - 1] - colpr[i + 1][j], dpdown[i][j - 1] - colpr[i + 1][j]));
                dpdown[i][j] += best;
                best += grid[i][j];
            }
        }
        best = 0;
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; ++j) {
                best = max(best, dpup[i][j]);
                best = max(best, dpdown[i][j]);
            }
        }
        return best;
    }
};

Go solution:
func maximumScore(grid [][]int) int64 {
    n := len(grid)
    if n == 1 {
        return 0
    }
    dp := make([][]int64, n + 1)
    dp2 := make([][]int64, n + 1)
    for i := range dp {
        dp[i] = make([]int64, n + 1 - i)
        dp2[i] = make([]int64, n + 1 - i)
    }
    max_h := make([]int64, n + 1)
    for j := 1; j < n; j++ {
        // dp_0 takes into account only those dp[k][m] having k+m <= h
        dp_0 := int64(0)
        for h := range dp {
            for i := 0; i <= h; i++ {
                if v := dp[i][h - i]; v > dp_0 {
                    dp_0 = v
                }
            }
            dp2[h][0] = dp_0
            if h < n {
                // all values dp[k][m] should be increased by grid[h][j-1] for next h, meaning that maximum is also increased by same value
                dp_0 += int64(grid[h][j - 1])
            }
            for i := 0; i <= h; i++ {
                // now also take into account dp[k][m] having k+m > h
                if max_h[h] > dp2[h][0] {
                    dp2[h][0] = max_h[h]
                }
            }
            // s is to optimize sum of values from current column
            // max is the maximum value among dp[h] to update max_h[h]
            s, max := int64(0), dp2[h][0]
            for l := 1; l <= n - h; l++ {
                s += int64(grid[h + l - 1][j])
                dp2[h][l] = max_h[h + l] + s
                if dp2[h][l] > max {
                    max = dp2[h][l]
                }
            }
            // it is safe since next iteration we consider only max_h[i] where i >= h + 1
            max_h[h] = max
        }
        dp, dp2 = dp2, dp
    }
    // now find the maximum
    res := dp[0][0]
    for _, r := range dp {
        for _, v := range r {
            if v > res {
                res = v
            }
        }
    }
    return res
}

Java solution:
class Solution {

    Long dp[][][];

    long solve(int grid[][], int col, int last1, int last2)
    {
        int n = grid.length;

        if(col >= n)
        {
            return 0;
        }

        if(dp[col][last1][last2] != null)
        {
            return dp[col][last1][last2];
        }

        long fromLast2 = 0;

        for(int i=0; i<last2; i++)
        {
            fromLast2 = fromLast2 + grid[i][col];
        }

        // Case I

        // don't take anything from this column, just take contribution of last2

        long ans = fromLast2 + solve(grid, col + 1, 0, last1);

        long sum = 0;

        // Case II

        if(col + 1 < n)
        {
            // take from this column and block next column for taking it
            // also note here we are passing last2 as 0 because last1 will overlapped and exceed with last2
            for(int i=last1; i<n; i++)
            {
                sum = sum + grid[i][col];
                ans = Math.max(ans, sum + solve(grid, col + 1, i + 1, 0));
            }
        }

        // Case III

        // here mark the current columns as block by manipulating next last2
        // also take into consideration last2 which we got here
        for(int i=0; i<n; i++)
        {
            if(i < last2)
            {
                fromLast2 = fromLast2 - grid[i][col];
            }
            ans = Math.max(ans, fromLast2 + solve(grid, col + 1, 0, i + 1));
        }

        dp[col][last1][last2] = ans;

        return ans;
    }

    public long maximumScore(int[][] grid) {
        int n = grid.length;

        dp = new Long[n + 1][n + 1][n + 1];

        return solve(grid, 0, 0, 0);
    }
}

JavaScript solution:
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maximumScore = function(grid) {
    const n = grid.length;
    if (n === 1) return 0;

    // Add a zero column to the grid to handle boundary conditions
    const newGrid = grid.map(row => [...row, 0]);
    const colpr = Array.from({ length: n + 1 }, () => new Array(newGrid[0].length).fill(0));

    // Compute prefix sums for each column
    for (let j = 0; j < newGrid[0].length; j++) {
        for (let i = 0; i < n; i++) {
            colpr[i + 1][j] = colpr[i][j] + newGrid[i][j];
        }
    }

    if (n === 2) {
        return Math.max(colpr[n][0], colpr[n][1]);
    }

    let best = 0;
    const dpup = Array.from({ length: n }, () => new Array(n).fill(0));
    const dpdown = Array.from({ length: n }, () => new Array(n).fill(0));
    let rmax = new Array(n).fill(0);
    let onesuf = new Array(n).fill(0);
    let twosuf = new Array(n).fill(0);

    // Initialize for column 0
    for (let i = 0; i < n; i++) {
        dpup[i][0] = colpr[i + 1][1];
    }

    // Initialize for column 1
    for (let i = 0; i < n; i++) {
        dpup[i][1] = colpr[i + 1][0] + colpr[i + 1][2];
    }
    for (let i = 0; i < n - 1; i++) {
        dpdown[i][1] = dpup[n - 1][0] + (colpr[i + 1][2] - colpr[i + 1][1]);
    }

    // Initialize for column 2
    for (let i = 0; i < n; i++) {
        dpup[i][2] = colpr[i + 1][1] + colpr[i + 1][3];
        let currentBest = Math.max(dpup[n - 1][0] - colpr[i + 1][1], 0);
        for (let k = 0; k <= i; k++) {
            currentBest = Math.max(currentBest, dpup[k][1] - colpr[k + 1][1] - colpr[k + 1][2]);
        }
        dpup[i][2] += currentBest;
    }
    for (let i = 0; i < n - 1; i++) {
        dpdown[i][2] = colpr[i + 1][3];
        let currentBest = 0;
        for (let k = n - 1; k >= i; k--) {
            currentBest = Math.max(currentBest, dpdown[k][1] - colpr[i + 1][2]);
        }
        for (let k = n - 1; k >= i; k--) {
            currentBest = Math.max(currentBest, dpup[k][1] - colpr[i + 1][2]);
        }
        dpdown[i][2] += currentBest;
    }

    // Process columns from 3 onwards
    for (let j = 3; j < n; j++) {
        let a = 0;
        for (let k = 0; k < n; k++) {
            rmax[k] = Math.max(rmax[k], dpup[k][j - 3]);
            a = Math.max(a, rmax[k]);
        }
        for (let k = 0; k < n; k++) {
            rmax[k] = Math.max(rmax[k], dpdown[k][j - 3]);
            a = Math.max(a, rmax[k]);
        }

        let one = 0, two = 0;
        let onep = 0, twop = 0;
        for (let k = n - 1; k >= 0; k--) {
            if (dpup[k][j - 2] > one) {
                one = dpup[k][j - 2];
                onep = k;
            }
            onesuf[k] = dpup[k][j - 2];
            if (k !== n - 1) {
                onesuf[k] = Math.max(onesuf[k], onesuf[k + 1]);
            }
        }
        for (let k = n - 1; k >= 0; k--) {
            if (dpdown[k][j - 2] > two) {
                two = dpdown[k][j - 2];
                twop = k;
            }
            twosuf[k] = dpdown[k][j - 2];
            if (k !== n - 1) {
                twosuf[k] = Math.max(twosuf[k], twosuf[k + 1]);
            }
        }

        for (let i = 0; i < n; i++) {
            dpup[i][j] = colpr[i + 1][j - 1] + colpr[i + 1][j + 1];
            let currentBest = 0;
            a = Math.max(a, dpup[i][j - 1] - colpr[i + 1][j - 1] - colpr[i + 1][j]);
            const oneVal = onesuf[i] - colpr[i + 1][j - 1];
            const oneMin = Math.min(onep, i);
            const onePrev = one - colpr[oneMin + 1][j - 1];
            if (oneVal > onePrev) {
                one = onesuf[i];
                onep = i;
            }
            const twoVal = twosuf[i] - colpr[i + 1][j - 1];
            const twoMin = Math.min(twop, i);
            const twoPrev = two - colpr[twoMin + 1][j - 1];
            if (twoVal > twoPrev) {
                two = twosuf[i];
                twop = i;
            }
            dpup[i][j] += Math.max(currentBest, Math.max(a, Math.max(oneVal, twoVal)));
        }

        let currentBest = 0;
        for (let i = n - 1; i >= 0; i--) {
            dpdown[i][j] = colpr[i + 1][j + 1];
            currentBest = Math.max(currentBest, Math.max(dpup[i][j - 1] - colpr[i + 1][j], dpdown[i][j - 1] - colpr[i + 1][j]));
            dpdown[i][j] += currentBest;
            currentBest += newGrid[i][j];
        }
    }

    let result = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            result = Math.max(result, dpup[i][j], dpdown[i][j]);
        }
    }

    return result;
};

Python solution:
class Solution:
    # zigzag max weight path 
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n==1: return 0
        grid = tuple(zip(*grid)) # transpose
        ri = [[-1]*n for i in range(n)] # go right
        le = [[-1]*n for i in range(n)] # go left
        for i in range(n):
            ri[i][0] = grid[i][0] # start at each row
        le[1][n-1] = grid[1][n-1] # first row black, start at (1,n-1)
        for i in range(n-1):
            # go right
            for j in range(n-1):
                if ri[i][j]==-1: continue
                ri[i][j+1] = max(ri[i][j+1],ri[i][j]+grid[i][j+1])
                if i+1<n-1:
                    ri[i+1][j+1] = max(ri[i+1][j+1],ri[i][j]+grid[i+1][j+1])
            if i+2<n:
                le[i+2][-1] = max(le[i+2][-1],ri[i][-1]+grid[i+2][-1])
            if i+3<n:
                le[i+3][-1] = max(le[i+3][-1],ri[i][-1]+grid[i+3][-1])
            if i+4<n: # i+1 and i+3 are black
                le[i+4][n-1]=max(le[i+4][-1],ri[i][-1]+grid[i+4][-1]+sum(grid[i+2]))
            # go left
            for j in range(n-1,0,-1):
                if le[i][j]==-1: continue
                le[i][j-1] = max(le[i][j-1],le[i][j]+grid[i][j-1])
                le[i+1][j-1] = max(le[i+1][j-1],le[i][j]+grid[i+1][j-1])
            if i+1<n: # must go right at next row, no 3 white row
                ri[i+1][0] = max(ri[i+1][0],le[i][0]+grid[i+1][0])
        #
        for j in range(n-1,0,-1): # last row, only go left
            if le[-1][j]==-1: continue
            le[-1][j-1] = max(le[-1][j-1],le[-1][j]+grid[-1][j-1])
        imax1 = max(ri[i][-1] for i in range(n))
        imax2 = max(le[i][0] for i in range(n))
        return max(imax1,imax2)

Ruby solution:
def maximum_score(grid)
  n = grid.size
  return 0 if n == 1

  new_grid = grid.map { |row| row + [0] }
  m = new_grid[0].size
  colpr = Array.new(n+1) { Array.new(m, 0) }
  (0...m).each do |j|
    (0...n).each { |i| colpr[i+1][j] = colpr[i][j] + new_grid[i][j] }
  end
  return [colpr[n][0], colpr[n][1]].max if n == 2

  dpup = Array.new(n) { Array.new(n, 0) }
  dpdown = Array.new(n) { Array.new(n, 0) }
  rmax = Array.new(n, 0)
  onesuf = Array.new(n, 0)
  twosuf = Array.new(n, 0)

  (0...n).each { |i| dpup[i][0] = colpr[i+1][1] }
  (0...n).each { |i| dpup[i][1] = colpr[i+1][0] + colpr[i+1][2] }
  (0...(n-1)).each { |i| dpdown[i][1] = dpup[n-1][0] + (colpr[i+1][2] - colpr[i+1][1]) }

  (0...n).each do |i|
    dpup[i][2] = colpr[i+1][1] + colpr[i+1][3]
    current_best = [dpup[n-1][0] - colpr[i+1][1], 0].max
    (0..i).each { |k| current_best = [current_best, dpup[k][1] - colpr[k+1][1] - colpr[k+1][2]].max }
    dpup[i][2] += current_best
  end
  (0...(n-1)).each do |i|
    dpdown[i][2] = colpr[i+1][3]
    current_best = 0
    (i..(n-1)).to_a.reverse_each { |k| current_best = [current_best, dpdown[k][1] - colpr[i+1][2]].max }
    (i..(n-1)).to_a.reverse_each { |k| current_best = [current_best, dpup[k][1] - colpr[i+1][2]].max }
    dpdown[i][2] += current_best
  end

  (3...n).each do |j|
    a = 0
    (0...n).each do |k|
      rmax[k] = [rmax[k], dpup[k][j-3]].max
      a = [a, rmax[k]].max
    end
    (0...n).each do |k|
      rmax[k] = [rmax[k], dpdown[k][j-3]].max
      a = [a, rmax[k]].max
    end

    one = 0
    two = 0
    onep = 0
    twop = 0
    (0...n).reverse_each do |k|
      if dpup[k][j-2] > one
        one = dpup[k][j-2]
        onep = k
      end
      onesuf[k] = dpup[k][j-2]
      onesuf[k] = [onesuf[k], onesuf[k+1]].max if k != n-1
    end
    (0...n).reverse_each do |k|
      if dpdown[k][j-2] > two
        two = dpdown[k][j-2]
        twop = k
      end
      twosuf[k] = dpdown[k][j-2]
      twosuf[k] = [twosuf[k], twosuf[k+1]].max if k != n-1
    end

    (0...n).each do |i|
      dpup[i][j] = colpr[i+1][j-1] + colpr[i+1][j+1]
      current_best = 0
      a = [a, dpup[i][j-1] - colpr[i+1][j-1] - colpr[i+1][j]].max
      one_val = onesuf[i] - colpr[i+1][j-1]
      one_prev = one - colpr[[onep, i].min + 1][j-1]
      if one_val > one_prev
        one = onesuf[i]
        onep = i
      end
      two_val = twosuf[i] - colpr[i+1][j-1]
      two_prev = two - colpr[[twop, i].min + 1][j-1]
      if two_val > two_prev
        two = twosuf[i]
        twop = i
      end
      dpup[i][j] += [current_best, a, one_val, two_val].max
    end

    current_best = 0
    (0...n).reverse_each do |i|
      dpdown[i][j] = colpr[i+1][j+1]
      current_best = [current_best, dpup[i][j-1] - colpr[i+1][j], dpdown[i][j-1] - colpr[i+1][j]].max
      dpdown[i][j] += current_best
      current_best += new_grid[i][j]
    end
  end

  result = 0
  (0...n).each { |i| (0...n).each { |j| result = [result, dpup[i][j], dpdown[i][j]].max } }
  result
end