<p>You are given a 2D matrix <code>grid</code> of size <code>n x n</code>. Initially, all cells of the grid are colored white. In one operation, you can select any cell of indices <code>(i, j)</code>, and color black all the cells of the <code>j<sup>th</sup></code> column starting from the top row down to the <code>i<sup>th</sup></code> row.</p>

<p>The grid score is the sum of all <code>grid[i][j]</code> such that cell <code>(i, j)</code> is white and it has a horizontally adjacent black cell.</p>

<p>Return the <strong>maximum</strong> score that can be achieved after some number of operations.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">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]]</span></p>

<p><strong>Output:</strong> <span class="example-io">11</span></p>

<p><strong>Explanation:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/05/11/one.png" style="width: 300px; height: 200px;" />
<p>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 <code>grid[3][0] + grid[1][2] + grid[3][3]</code> which is equal to 11.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">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]]</span></p>

<p><strong>Output:</strong> <span class="example-io">94</span></p>

<p><strong>Explanation:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/05/11/two-1.png" style="width: 300px; height: 200px;" />
<p>We perform operations on 1, 2, and 3 down to rows 1, 4, and 0, respectively. The score of the resulting grid is <code>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]</code> which is equal to 94.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;=&nbsp;n == grid.length &lt;= 100</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 1:
            return 0

        prev_col_w = [0 for _ in range(n+1)]
        prev_col_wo = [0 for _ in range(n+1)]
        for j in range(1, n):  # for each current column
            # maximum score of previous column when row 0 to i-1 is black (note that
            #   if i == 0, i.e. the top cell, has no black above it)
            # '_w' is including the score contribution of the current column
            # '_wo' is excluding the score contribution of the current column
            cur_col_w = [0 for _ in range(n+1)]
            cur_col_wo = [0 for _ in range(n+1)]
            for i in range(n+1):
                # iterate current column by taking the top i rows (i.e. cells) with the following assumption:
                #   assume previous column (column idx = j-1) is black from row 0 to i-1
                #     (no that if i == 0, previous column has no black cell)
                prev_col_val = 0
                cur_col_val = 0
                # initialize current cell score by adding from row 0 to current row (in current column only)
                for p in range(i):
                    cur_col_val += grid[p][j]
                for k in range(n+1):
                    # now, assume current column cells are black from row 0 to k-1
                    #   thus, we need to remove these cell scores from current cell score
                    if k > 0 and k <= i:
                        cur_col_val -= grid[k-1][j]
                    # similarly, if the current black goes beyond (i.e. below) the previous black boundary
                    #   (which is down to row i-1 set in the upper-level loop), the current cell back
                    #   can cause the previous cell which is left to it contribute to score, and hence
                    #   we add previous cell score
                    if k > i:
                        prev_col_val += grid[k-1][j-1]
                    # for the previous column score which excluding previous cells, we can add
                    #   the cumulative score computed above to get the final previous column score.
                    # for the score that already includes previous cells, we don't add
                    # for current column score without current cell scores, simply update the number
                    #   with the maximum of the above two
                    cur_col_wo[k] = max(cur_col_wo[k], prev_col_val + prev_col_wo[i], prev_col_w[i])
                    # for current column score including current cells, we also add current cell
                    #   cumulative score computed above
                    cur_col_w[k] = max(cur_col_w[k], \
                        cur_col_val + prev_col_val + prev_col_wo[i], cur_col_val + prev_col_w[i])
            prev_col_w = cur_col_w
            prev_col_wo = cur_col_wo
        return max(cur_col_w)

17500