Uva - 108 Maximum Sum

#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n;
    cin >> n;
   
    // ciallo：存放原始的 n×n 矩陣（使用 1-based 索引）
    vector<vector<int>> ciallo(n+1, vector<int>(n+1, 0));
    // dp：存放二維前綴和
    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
   
    // 輸入矩陣
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> ciallo[i][j];
        }
    }

    // 計算二維前綴和
    // dp[i][j] 代表從 (1,1) 到 (i,j) 的矩形區域內所有元素的總和
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + ciallo[i][j];
        }
    }      
   
    // 枚舉所有子矩陣，找出最大子矩陣和
    int max = -1e9;
    int tmp;
    for(int i = 1; i <= n; ++i){        // 子矩陣的上邊界列
        for(int j = 1; j <= n; ++j){    // 子矩陣的左邊界行
            for(int r = i; r <= n; ++r){    // 子矩陣的下邊界列
                for(int k = j; k <= n; ++k){ // 子矩陣的右邊界行
                    // 利用前綴和公式計算以 (i,j) 為左上角、(r,k) 為右下角的子矩陣總和
                    tmp = dp[r][k] - dp[i-1][k] - dp[r][j-1] + dp[i-1][j-1];
                    if(tmp > max) max = tmp;
                }
            }
        }
    }
   
    cout << max << endl;
}
//   ᶜⁱᵃˡˡᵒ～(∠・ω< )⌒☆

/*
這段程式的核心邏輯是最大子矩陣和問題，流程如下：

1. 前綴和預處理：dp[i][j] 儲存左上角 (1,1) 到右下角 (i,j)`的矩形總和，讓任意子矩陣的和可以 O(1) 查詢。

2. 子矩陣和公式：對於左上角 (i,j)、右下角 (r,k) 的子矩陣，其總和為：
   dp[r][k] - dp[i-1][k] - dp[r][j-1] + dp[i-1][j-1]
3. 枚舉所有子矩陣：四層迴圈暴力枚舉所有可能的子矩陣，整體時間複雜度為 O(n⁴)。
*/