筆記：【演算法新手村】[初階]筆記05 - 前綴和(二維)

題目翻譯

輸入 (Input)輸入包含一個 N×N 的整數陣列。

• 第一行是一個正整數 N，代表這個正方形二維陣列的大小。
• 接下來有 N² 個整數，以空白字元（換行或空格）隔開。
• 這些 N² 個整數以「列優先順序（Row-major order）」組成陣列（即：第一列的所有數字由左至右、接著第二列由左至右，依此類推）。
• N 的最大值為 100。
• 陣列中的數值範圍介於 [-127, 127] 之間。

輸出 (Output)輸出為 最大子矩陣（Maximal Sub-rectangle） 的總和。

暴力解解題思路

首先我們定義前綴和矩陣S[i][j]代表從左上角(1, 1)到右下角(i, j)這個矩形內所有數字的總和。
再來計算子矩陣和(任意一個由 (r1, c1) 到 (r2, c2) 構成的矩形和)，我們可以透過暴力枚舉2個座標去找到最大子矩陣。

注意事項

這題因為N很小加上只需要查詢一次，所以可以使用暴力解(時間複雜度為O(n⁴))，如果N很大，暴力解很
有可能會TLE!

程式碼實作 (C++)

#include <iostream>
#include <climits>

using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;

    int arr[101][101] = {0};
    int sum[101][101] = {0};

    int Min = 0;
    int Max = INT_MIN;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &arr[i][j]);
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
        }
    }

    // 暴力枚舉2個座標(r1,c1)跟(r2,c2)
    for(int r1 = 1 ; r1 <= n ; r1++){
        for(int c1 = 1 ;  c1 <= n ; c1++){
            for(int r2 = r1 ; r2 <= n ; r2++){
                for(int c2 = c1 ; c2 <= n ; c2++){
                    int cur_sum = sum[r2][c2] - sum[r2][c1-1] - sum[r1-1][c2] + sum[r1-1][c1-1];
                    if(cur_sum > Max){
                        Max = cur_sum;
                    }
                }
            }
        }
    }

    printf("%d\n",Max);

    return 0;
}