問題描述

N×N 矩陣（N≤100），尋找任意子矩陣（連續行、連續列）使元素和最大。輸出最大和。

算法思路：枚舉上下邊界 + 一維最大子段和

1. 預計算列前綴和 sum[col][row] = 第 col 列前 row 行和。
2. 枚舉上邊界 top (1~n) 和下邊界 bottom (top~n)。
3. 對每一列，區間和 = sum[col][bottom] - sum[col][top-1]，得到一維數組。
4. 對一維數組跑最大子段和（Kadane 算法），得到當前行區間的最大子矩陣和。
5. 全局最大值更新。

代碼實現

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

const int MAXN = 105;
int a[MAXN][MAXN];
int col_sum[MAXN][MAXN]; // col_sum[c][r] = column c, rows 1..r sum

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i=1;i<=n;++i)
            for (int j=1;j<=n;++j)
                scanf("%d", &a[i][j]);
        
        // 列前綴和
        for (int c=1;c<=n;++c) {
            col_sum[c][0] = 0;
            for (int r=1;r<=n;++r)
                col_sum[c][r] = col_sum[c][r-1] + a[r][c];
        }
        
        int ans = INT_MIN;
        // 枚舉上下行
        for (int top=1; top<=n; ++top) {
            for (int bottom=top; bottom<=n; ++bottom) {
                int cur = 0, best = INT_MIN;
                for (int c=1; c<=n; ++c) {
                    int val = col_sum[c][bottom] - col_sum[c][top-1];
                    cur = max(val, cur + val); // Kadane
                    best = max(best, cur);
                }
                ans = max(ans, best);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點解析

1. 列前綴和：將二維區間和查詢降為 O(1)，預處理 O(n²)。
2. 枚舉行對：O(n²) 對，每對處理 O(n) 列，總 O(n³) = 10⁶，輕鬆通過。
3. Kadane 算法：一維最大子段和，cur = max(val, cur+val) 同時處理負數情況。
4. 初始值：ans = INT_MIN 保證全負數矩陣也能正確取最大值（最小負數）。

複雜度

• 時間：O(n³)，n=100 時 100 万循環，C++ < 0.1s。
• 空間：O(n²)。

變體延伸

• 輸出子矩陣座標：記錄 Kadane 過程中的左右邊界。
• 矩陣元素為浮點數/長整型：調整類型即可。
• 圓形/任意形狀區域：需前綴和矩陣 + 幾何判斷，不再適用此模板。

總結

POJ 1050 是「二維最大子矩陣和」的經典入門題。核心技巧：

1. 固定上下邊界，將二維問題降維為一維。
2. 列前綴和 O(1) 獲取列區間和。
3. Kadane 算法 O(n) 解一維最大子段和。

此 O(n³) 算法是二維最大子陣列和的標準解法，N≤100 時最優。掌握此模板，可解決所有「連續子矩陣極值」問題。