3225. Maximum Score From Grid Operations

Difficulty: Hard

Topics: Principal , Array , Dynamic Programming , Matrix , Prefix Sum , Biweekly Contest 135

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 jᵗʰ column starting from the top row down to the iᵗʰ 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.…