3225. Maximum Score From Grid Operations

// 演算法 / Algorithm: 由左往右掃描,維護 dp[h[j-1]][h[j]] = 已完成第 0..j-1 欄貢獻的最大分數。
// 轉移時枚舉下一欄高度 c,把第 j 欄延後的貢獻 S(j, h[j], max(h[j-1], c)) 加進去。
// Sweep columns left-to-right; dp[a][b] = best score with h[j-1]=a, h[j]=b and columns 0..j-1
// fully booked. Each transition picks h[j+1]=c and adds column j's deferred contribution.

#include <stdlib.h>     // 提供基本型態 / basic types
#include <string.h>     // 提供 memcpy / for memcpy
#include <limits.h>     // 提供 LLONG_MIN / for LLONG_MIN

long long maximumScore(int** grid, int gridSize, int* gridColSize) {
    int n = gridSize;                                   // n 為網格邊長 / n is the grid side length

    // static 讓陣列在 BSS 區,避免爆掉函式呼叫堆疊 / static keeps arrays off the call stack
    static long long colSum[101][102];                  // colSum[j][k]=第 j 欄前 k 列之和 / column-j prefix sum
    static long long dp[102][102], ndp[102][102];       // 滾動兩層 / rolling DP layers
    const long long NEG = LLONG_MIN / 4;                // 標記不可達狀態,除以 4 避免相加溢位 / sentinel for unreachable, /4 avoids overflow when added

    // 預計算每欄的前綴和,讓任意列區間和能 O(1) 取得 / precompute per-column prefix sums for O(1) range queries
    for (int j = 0; j < n; j++) {                       // 對每一欄 / for each column
        colSum[j][0] = 0;                               // 空前綴和為 0 / empty prefix sums to 0
        for (int i = 0; i < n; i++) {                   // 從上到下累加 / accumulate top-down
            // 強制轉成 long long,避免在 int 範圍相加時溢位 / cast to long long to avoid int overflow
            colSum[j][i + 1] = colSum[j][i] + (long long)grid[i][j];
        }
    }

    // 初始化 j=0 的狀態 / initialize states for column j=0
    for (int a = 0; a <= n; a++)                        // a = h[-1] (虛擬左鄰) / a = h[-1] (virtual left neighbor)
        for (int b = 0; b <= n; b++)                    // b = h[0]
            dp[a][b] = NEG;                             // 預設不可達 / default unreachable
    for (int b = 0; b <= n; b++)                        // 規定 h[-1]=0,所以只有 a=0 合法 / convention h[-1]=0, only a=0 is valid
        dp[0][b] = 0;                                   // 還沒加任何貢獻 / no contributions added yet

    // 主迴圈:由 j 轉移到 j+1 / main loop: transition from column j to column j+1
    for (int j = 0; j + 1 < n; j++) {
        // 重置 ndp / reset ndp
        for (int b = 0; b <= n; b++)
            for (int c = 0; c <= n; c++)
                ndp[b][c] = NEG;

        for (int b = 0; b <= n; b++) {                  // b = h[j] = 上一狀態的 b / b is current column's height
            for (int c = 0; c <= n; c++) {              // c = h[j+1] = 想決定的下一欄高度 / c is next column's height
                long long best = NEG;                   // 在所有 a 中取最大 / take max over all a
                for (int a = 0; a <= n; a++) {          // a = h[j-1] = 上一狀態的 a / a is previous-previous column's height
                    if (dp[a][b] <= NEG) continue;      // 跳過不可達狀態 / skip unreachable
                    int top = (a > c) ? a : c;          // top = max(h[j-1], h[j+1]) 決定第 j 欄白色貢獻邊界 / top sets the upper bound for column j's white contributions
                    // 第 j 欄的貢獻:第 b 列到第 top-1 列的數值和,若 b ≥ top 則為 0
                    // Column j's contribution: sum of rows [b, top); if b ≥ top, no white cell qualifies
                    long long contrib = (b < top) ? (colSum[j][top] - colSum[j][b]) : 0;
                    long long val = dp[a][b] + contrib; // 加上延後的貢獻 / add deferred contribution
                    if (val > best) best = val;         // 更新最大值 / update max
                }
                ndp[b][c] = best;                       // 寫入新狀態 / store new state
            }
        }
        memcpy(dp, ndp, sizeof(dp));                    // 滾動:把 ndp 變成下一輪的 dp / roll layers: ndp becomes dp
    }

    // 最後一欄(j = n-1)還欠一次貢獻,用 h[n]=0 套公式 / last column still has a deferred contribution; apply with h[n]=0
    long long ans = 0;                                  // 答案至少為 0(全不操作) / answer is at least 0 (no operations)
    int j = n - 1;
    for (int a = 0; a <= n; a++) {
        for (int b = 0; b <= n; b++) {
            if (dp[a][b] <= NEG) continue;              // 不可達跳過 / skip unreachable
            // h[n]=0,top = max(a, 0) = a,故貢獻為 [b, a) 之和
            // h[n]=0 makes top = a, so contribution is sum over rows [b, a)
            long long contrib = (b < a) ? (colSum[j][a] - colSum[j][b]) : 0;
            long long val = dp[a][b] + contrib;
            if (val > ans) ans = val;                   // 取最大 / track max
        }
    }
    return ans;                                         // 回傳最大分數 / return the max score
}

// 演算法 / Algorithm: 同 C 版本 — 由左往右 DP,dp[a][b] 表示已完成 0..j-1 欄貢獻、且 h[j-1]=a、h[j]=b 的最大分數。
// Same as the C version: left-to-right DP where dp[a][b] is the best score with columns 0..j-1
// fully booked, h[j-1]=a, h[j]=b. Transitions choose h[j+1]=c and pay column j's deferred contribution.

#include <vector>       // std::vector 動態陣列 / std::vector dynamic array
#include <climits>      // LLONG_MIN
#include <algorithm>    // std::max
using namespace std;

class Solution {
public:
    long long maximumScore(vector<vector<int>>& grid) {
        int n = grid.size();                                   // n = 邊長 / n = side length

        // 每欄前綴和:colSum[j][k] = grid[0..k-1][j] 之和 / per-column prefix sum
        // vector<vector<long long>> 為二維動態陣列,用 long long 避免 overflow
        // 2D dynamic array of long long to prevent overflow
        vector<vector<long long>> colSum(n, vector<long long>(n + 1, 0));
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                colSum[j][i + 1] = colSum[j][i] + grid[i][j];  // 自動提升為 long long / auto-promotes to long long
            }
        }

        const long long NEG = LLONG_MIN / 4;                   // 不可達狀態哨兵 / unreachable sentinel
        // dp[a][b]:目前欄為 j,a = h[j-1],b = h[j] / dp[a][b]: a is h[j-1], b is h[j] for current j
        vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, NEG));
        for (int b = 0; b <= n; b++) dp[0][b] = 0;             // 初始 j=0:只有 a=0 合法 / init j=0: only a=0 valid

        // 一欄欄推進 / advance column by column
        for (int j = 0; j + 1 < n; j++) {
            // 新一層的 dp,先全填 NEG / fresh layer, default NEG
            vector<vector<long long>> ndp(n + 1, vector<long long>(n + 1, NEG));
            for (int b = 0; b <= n; b++) {                     // b = h[j]
                for (int c = 0; c <= n; c++) {                 // c = h[j+1]
                    long long best = NEG;
                    for (int a = 0; a <= n; a++) {             // a = h[j-1]
                        if (dp[a][b] <= NEG) continue;         // 不可達 / unreachable
                        int top = max(a, c);                   // 第 j 欄白色貢獻的上邊界 / upper bound of column j's white contribution
                        // 用前綴和 O(1) 算第 j 欄列 [b, top) 之和 / O(1) range sum of column j rows [b, top)
                        long long contrib = (b < top) ? (colSum[j][top] - colSum[j][b]) : 0;
                        best = max(best, dp[a][b] + contrib);  // 取最佳 / keep the best
                    }
                    ndp[b][c] = best;
                }
            }
            dp = move(ndp);                                    // 滾動,move 避免複製成本 / roll layers; move avoids deep copy
        }

        // 最後加上 j=n-1 欄的延後貢獻,假設右邊高度為 0 / pay column n-1's deferred contribution with h[n]=0
        long long ans = 0;
        int j = n - 1;
        for (int a = 0; a <= n; a++) {
            for (int b = 0; b <= n; b++) {
                if (dp[a][b] <= NEG) continue;
                // h[n]=0,故 top = max(a, 0) = a,貢獻為列 [b, a) 之和
                // h[n]=0 → top = a, contribution = sum over rows [b, a)
                long long contrib = (b < a) ? (colSum[j][a] - colSum[j][b]) : 0;
                ans = max(ans, dp[a][b] + contrib);            // std::max 比較取大者 / std::max picks the larger
            }
        }
        return ans;                                            // 最終答案 / final answer
    }
};