Skip to content

3225. Maximum Score From Grid Operations

Description

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:

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:

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

Solutions

Solution 1: Dynamic Programming + Prefix Sum

Thinking

Each column is painted black from the top for some height; a white cell scores only if a neighbor column is black there. \(n\le 100\), so enumerating height tuples is \((n+1)^n\). Column \(j\)'s score depends only on its height and its two neighbors, which suggests a column DP.

\(f[h_1][h_2]\) is the best score with current height \(h_1\) and previous height \(h_2\). When enumerating the next height, \(\max(h_2,h_p)\) makes the addend piecewise, so prefix/suffix maxima over \(h_2\) drop a column from \(O(n^3)\) to \(O(n^2)\). Column prefix sums precompute white-range totals.

For each column \(j\), let \(k[j] \in \{0, 1, \ldots, n\}\) be the number of cells colored black from the top. A white cell \((i, j)\) scores if and only if at least one horizontally adjacent cell is black, and it is counted only once. The contribution of column \(j\) is therefore:

\[ \max\bigl(0,\ s[j][\max(k[j-1], k[j+1])] - s[j][k[j]]\bigr) \]

where \(s[j][h]\) is the prefix sum of the first \(h\) cells in column \(j\) (boundary column heights are treated as \(0\)).

Let \(f[h_1][h_2]\) be the maximum score after processing column \(j\) with \(k[j] = h_1\) and \(k[j-1] = h_2\). When choosing the next height \(hp = k[j+1]\):

\[ g[hp][h_1] = \max_{h_2}\bigl(f[h_1][h_2] + \max(0,\ s[j][\max(h_2, hp)] - s[j][h_1])\bigr) \]

Split the transition into \(h_2 \le hp\) and \(h_2 > hp\), and maintain prefix / suffix maxima so that each column costs \(O(n^2)\) instead of \(O(n^3)\).

The time complexity is \(O(n^3)\), and the space complexity is \(O(n^2)\), where \(n\) is the grid size.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        s = [[0] * (n + 1) for _ in range(n)]
        for j in range(n):
            for i, x in enumerate(grid):
                s[j][i + 1] = s[j][i] + x[j]
        f = [[-inf] * (n + 1) for _ in range(n + 1)]
        for h in range(n + 1):
            f[h][0] = 0
        for j in range(n - 1):
            g = [[-inf] * (n + 1) for _ in range(n + 1)]
            for h1 in range(n + 1):
                pre = [-inf] * (n + 2)
                pre[0] = f[h1][0]
                for h2 in range(1, n + 1):
                    pre[h2] = max(pre[h2 - 1], f[h1][h2])
                suf = [-inf] * (n + 2)
                for h2 in range(n, -1, -1):
                    v = -inf
                    if f[h1][h2] != -inf:
                        v = f[h1][h2] + max(0, s[j][h2] - s[j][h1])
                    suf[h2] = max(suf[h2 + 1], v)
                for hp in range(n + 1):
                    add = max(0, s[j][hp] - s[j][h1])
                    v1 = -inf if pre[hp] == -inf else pre[hp] + add
                    g[hp][h1] = max(v1, suf[hp + 1])
            f = g
        ans = 0
        for h1 in range(n + 1):
            for h2 in range(n + 1):
                if f[h1][h2] != -inf:
                    ans = max(ans, f[h1][h2] + max(0, s[-1][h2] - s[-1][h1]))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public long maximumScore(int[][] grid) {
        int n = grid.length;
        final long inf = Long.MIN_VALUE / 2;
        long[][] s = new long[n][n + 1];
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < n; ++i) {
                s[j][i + 1] = s[j][i] + grid[i][j];
            }
        }
        long[][] f = new long[n + 1][n + 1];
        for (long[] row : f) {
            Arrays.fill(row, inf);
        }
        for (int h = 0; h <= n; ++h) {
            f[h][0] = 0;
        }
        for (int j = 0; j < n - 1; ++j) {
            long[][] g = new long[n + 1][n + 1];
            for (long[] row : g) {
                Arrays.fill(row, inf);
            }
            for (int h1 = 0; h1 <= n; ++h1) {
                long[] pre = new long[n + 2];
                pre[0] = f[h1][0];
                for (int h2 = 1; h2 <= n; ++h2) {
                    pre[h2] = Math.max(pre[h2 - 1], f[h1][h2]);
                }
                long[] suf = new long[n + 2];
                Arrays.fill(suf, inf);
                for (int h2 = n; h2 >= 0; --h2) {
                    long v = f[h1][h2] == inf ? inf : f[h1][h2] + Math.max(0, s[j][h2] - s[j][h1]);
                    suf[h2] = Math.max(suf[h2 + 1], v);
                }
                for (int hp = 0; hp <= n; ++hp) {
                    long add = Math.max(0, s[j][hp] - s[j][h1]);
                    long v1 = pre[hp] == inf ? inf : pre[hp] + add;
                    g[hp][h1] = Math.max(v1, suf[hp + 1]);
                }
            }
            f = g;
        }
        long ans = 0;
        for (int h1 = 0; h1 <= n; ++h1) {
            for (int h2 = 0; h2 <= n; ++h2) {
                if (f[h1][h2] != inf) {
                    ans = Math.max(ans, f[h1][h2] + Math.max(0, s[n - 1][h2] - s[n - 1][h1]));
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    long long maximumScore(vector<vector<int>>& grid) {
        int n = grid.size();
        const long long inf = LLONG_MIN / 2;
        vector<vector<long long>> s(n, vector<long long>(n + 1));
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < n; ++i) {
                s[j][i + 1] = s[j][i] + grid[i][j];
            }
        }
        vector<vector<long long>> f(n + 1, vector<long long>(n + 1, inf));
        for (int h = 0; h <= n; ++h) {
            f[h][0] = 0;
        }
        for (int j = 0; j < n - 1; ++j) {
            vector<vector<long long>> g(n + 1, vector<long long>(n + 1, inf));
            for (int h1 = 0; h1 <= n; ++h1) {
                vector<long long> pre(n + 2, inf), suf(n + 2, inf);
                pre[0] = f[h1][0];
                for (int h2 = 1; h2 <= n; ++h2) {
                    pre[h2] = max(pre[h2 - 1], f[h1][h2]);
                }
                for (int h2 = n; h2 >= 0; --h2) {
                    long long v = f[h1][h2] == inf ? inf : f[h1][h2] + max(0LL, s[j][h2] - s[j][h1]);
                    suf[h2] = max(suf[h2 + 1], v);
                }
                for (int hp = 0; hp <= n; ++hp) {
                    long long add = max(0LL, s[j][hp] - s[j][h1]);
                    long long v1 = pre[hp] == inf ? inf : pre[hp] + add;
                    g[hp][h1] = max(v1, suf[hp + 1]);
                }
            }
            f.swap(g);
        }
        long long ans = 0;
        for (int h1 = 0; h1 <= n; ++h1) {
            for (int h2 = 0; h2 <= n; ++h2) {
                if (f[h1][h2] != inf) {
                    ans = max(ans, f[h1][h2] + max(0LL, s[n - 1][h2] - s[n - 1][h1]));
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import "math"

func maximumScore(grid [][]int) int64 {
    n := len(grid)
    const inf = math.MinInt64 / 2
    s := make([][]int64, n)
    for j := 0; j < n; j++ {
        s[j] = make([]int64, n+1)
        for i := 0; i < n; i++ {
            s[j][i+1] = s[j][i] + int64(grid[i][j])
        }
    }
    f := make([][]int64, n+1)
    for i := range f {
        f[i] = make([]int64, n+1)
        for k := range f[i] {
            f[i][k] = inf
        }
    }
    for h := 0; h <= n; h++ {
        f[h][0] = 0
    }
    for j := 0; j < n-1; j++ {
        g := make([][]int64, n+1)
        for i := range g {
            g[i] = make([]int64, n+1)
            for k := range g[i] {
                g[i][k] = inf
            }
        }
        for h1 := 0; h1 <= n; h1++ {
            pre := make([]int64, n+2)
            pre[0] = f[h1][0]
            for h2 := 1; h2 <= n; h2++ {
                pre[h2] = max(pre[h2-1], f[h1][h2])
            }
            suf := make([]int64, n+2)
            for i := range suf {
                suf[i] = inf
            }
            for h2 := n; h2 >= 0; h2-- {
                v := int64(inf)
                if f[h1][h2] != inf {
                    v = f[h1][h2] + max(int64(0), s[j][h2]-s[j][h1])
                }
                suf[h2] = max(suf[h2+1], v)
            }
            for hp := 0; hp <= n; hp++ {
                add := max(int64(0), s[j][hp]-s[j][h1])
                v1 := int64(inf)
                if pre[hp] != inf {
                    v1 = pre[hp] + add
                }
                g[hp][h1] = max(v1, suf[hp+1])
            }
        }
        f = g
    }
    var ans int64
    for h1 := 0; h1 <= n; h1++ {
        for h2 := 0; h2 <= n; h2++ {
            if f[h1][h2] != inf {
                ans = max(ans, f[h1][h2]+max(int64(0), s[n-1][h2]-s[n-1][h1]))
            }
        }
    }
    return ans
}

Comments