class Solution { public: long long maximumScore(vector>& grid) { int n = grid.size(); if (n == 1) return 0; vector>> dp(n, vector>(n + 1, vector(n + 1, 0))); vector> prev_max(n + 1, vector(n + 1, 0)); vector> prev_suffix_max(n + 1, vector(n + 1, 0)); vector> col_sum(n, vector(n + 1, 0)); for (int c = 0; c < n; c++) { for (int r = 1; r <= n; r++) { col_sum[c][r] = col_sum[c][r - 1] + grid[r - 1][c]; } } for (int i = 1; i < n; i++) { for (int curr_h = 0; curr_h <= n; curr_h++) { for (int prev_h = 0; prev_h <= n; prev_h++) { if (curr_h <= prev_h) { long long extra = col_sum[i][prev_h] - col_sum[i][curr_h]; dp[i][curr_h][prev_h] = max(dp[i][curr_h][prev_h], prev_suffix_max[prev_h][0] + extra); } else { long long extra = col_sum[i - 1][curr_h] - col_sum[i - 1][prev_h]; dp[i][curr_h][prev_h] = max({dp[i][curr_h][prev_h], prev_max[prev_h][curr_h] + extra, prev_suffix_max[prev_h][curr_h]}); } } } for (int curr_h = 0; curr_h <= n; curr_h++) { long long cur_max = 0; for (int next_h = 0; next_h <= n; next_h++) { cur_max = max(cur_max, dp[i][next_h][curr_h]); prev_max[curr_h][next_h] = cur_max; } long long cur_suffix_max = 0; for (int next_h = n; next_h >= 0; next_h--) { cur_suffix_max = max(cur_suffix_max, dp[i][next_h][curr_h]); prev_suffix_max[curr_h][next_h] = cur_suffix_max; } } } long long ans = 0; for (int prev_h = 0; prev_h <= n; prev_h++) { ans = max(ans, prev_suffix_max[prev_h][0]); } return ans; } };

Time Complexity

Space Complexity