Skip to content

3225. Maximum Score From Grid Operations 👍

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 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
class Solution {
 public:
  long long maximumScore(vector<vector<int>>& grid) {
    const int n = grid.size();
    // prefix[j][i] := the sum of the first i elements in the j-th column
    vector<vector<long>> prefix(n, vector<long>(n + 1));
    // prevPick[i] := the maximum achievable score up to the previous column,
    // where the bottommost selected element in that column is in row (i - 1)
    vector<long> prevPick(n + 1);
    // prevSkip[i] := the maximum achievable score up to the previous column,
    // where the bottommost selected element in the column before the previous
    // one is in row (i - 1)
    vector<long> prevSkip(n + 1);

    for (int j = 0; j < n; ++j)
      for (int i = 0; i < n; ++i)
        prefix[j][i + 1] = prefix[j][i] + grid[i][j];

    for (int j = 1; j < n; ++j) {
      vector<long> currPick(n + 1);
      vector<long> currSkip(n + 1);
      // Consider all possible combinations of the number of current and
      // previous selected elements.
      for (int curr = 0; curr <= n; ++curr)
        for (int prev = 0; prev <= n; ++prev)
          if (curr > prev) {
            // 1. The current bottom is deeper than the previous bottom.
            // Get the score of grid[prev..curr)[j - 1] for pick and skip.
            const long score = prefix[j - 1][curr] - prefix[j - 1][prev];
            currPick[curr] = max(currPick[curr], prevSkip[prev] + score);
            currSkip[curr] = max(currSkip[curr], prevSkip[prev] + score);
          } else {
            // 2. The previous bottom is deeper than the current bottom.
            // Get the score of grid[curr..prev)[j] for pick only.
            const long score = prefix[j][prev] - prefix[j][curr];
            currPick[curr] = max(currPick[curr], prevPick[prev] + score);
            currSkip[curr] = max(currSkip[curr], prevPick[prev]);
          }
      prevPick = std::move(currPick);
      prevSkip = std::move(currSkip);
    }

    return ranges::max(prevPick);
  }
};

 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
class Solution {
  public long maximumScore(int[][] grid) {
    final int n = grid.length;
    // prefix[j][i] := the sum of the first i elements in the j-th column
    long[][] prefix = new long[n][n + 1];
    // prevPick[i] := the maximum achievable score up to the previous column,
    // where the bottommost selected element in that column is in row (i - 1)
    long[] prevPick = new long[n + 1];
    // prevSkip[i] := the maximum achievable score up to the previous column,
    // where the bottommost selected element in the column before the previous
    // one is in row (i - 1)
    long[] prevSkip = new long[n + 1];

    for (int j = 0; j < n; ++j)
      for (int i = 0; i < n; ++i)
        prefix[j][i + 1] = prefix[j][i] + grid[i][j];

    for (int j = 1; j < n; ++j) {
      long[] currPick = new long[n + 1];
      long[] currSkip = new long[n + 1];
      // Consider all possible combinations of the number of current and
      // previous selected elements.
      for (int curr = 0; curr <= n; ++curr)
        for (int prev = 0; prev <= n; ++prev)
          if (curr > prev) {
            // 1. The current bottom is deeper than the previous bottom.
            // Get the score of grid[prev..curr)[j - 1] for pick and skip.
            final long score = prefix[j - 1][curr] - prefix[j - 1][prev];
            currPick[curr] = Math.max(currPick[curr], prevSkip[prev] + score);
            currSkip[curr] = Math.max(currSkip[curr], prevSkip[prev] + score);
          } else {
            // 2. The previous bottom is deeper than the current bottom.
            // Get the score of grid[curr..prev)[j] for pick only.
            final long score = prefix[j][prev] - prefix[j][curr];
            currPick[curr] = Math.max(currPick[curr], prevPick[prev] + score);
            currSkip[curr] = Math.max(currSkip[curr], prevPick[prev]);
          }
      prevPick = currPick;
      prevSkip = currSkip;
    }

    return Arrays.stream(prevPick).max().getAsLong();
  }
}

 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
class Solution:
  def maximumScore(self, grid: list[list[int]]) -> int:
    n = len(grid)
    # prefix[j][i] := the sum of the first i elements in the j-th column
    prefix = [[0] * (n + 1) for _ in range(n)]
    # prevPick[i] := the maximum score up to the previous column, where the
    # bottommost selected element in the previous column is in row (i - 1)
    prevPick = [0] * (n + 1)
    # prevSkip[i] := the maximum score up to the previous column, where the
    # bottommost selected element in the column before the previous one is in
    # row (i - 1)
    prevSkip = [0] * (n + 1)

    for j in range(n):
      for i in range(n):
        prefix[j][i + 1] = prefix[j][i] + grid[i][j]

    for j in range(1, n):
      currPick = [0] * (n + 1)
      currSkip = [0] * (n + 1)
      # Consider all possible combinations of the number of current and
      # previous selected elements.
      for curr in range(n + 1):  # the number of current selected elements
        for prev in range(n + 1):  # the number of previous selected elements
          if curr > prev:
            # 1. The current bottom is deeper than the previous bottom.
            # Get the score of grid[prev..curr)[j - 1] for both pick and skip.
            score = prefix[j - 1][curr] - prefix[j - 1][prev]
            currPick[curr] = max(currPick[curr], prevSkip[prev] + score)
            currSkip[curr] = max(currSkip[curr], prevSkip[prev] + score)
          else:
            # 2. The previous bottom is deeper than the current bottom.
            # Get the score of grid[curr..prev)[j] for pick only.
            score = prefix[j][prev] - prefix[j][curr]
            currPick[curr] = max(currPick[curr], prevPick[prev] + score)
            currSkip[curr] = max(currSkip[curr], prevPick[prev])
      prevPick = currPick
      prevSkip = currSkip

    return max(prevPick)