問題描述

N×N 矩陣（N≤100），求任意連續子矩陣的最大元素和。輸入多組，EOF 結束。

算法：枚舉上下行 + 一維最大子段和

預計算列前綴和 sum[col][row]。枚舉上邊界 top、下邊界 bottom，對每列計算區間和構成一維數組，跑 Kadane 算法得最大子段和，更新全局答案。

代碼實現

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

const int MAXN = 105;
int a[MAXN][MAXN];
int col_sum[MAXN][MAXN];

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);
                    best = max(best, cur);
                }
                ans = max(ans, best);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點

1. 列前綴和：col_sum[c][r] 使列區間和 O(1) 獲取。
2. Kadane 算法：cur = max(val, cur+val) 同時處理全負數情況。
3. 初始值 INT_MIN：保證全負數矩陣正確取最大值（即最小負數）。
4. 多測試用例：while(~scanf("%d",&n)) 讀至 EOF。

複雜度

• 時間：O(n³) = 10⁶，C++ < 0.1s。
• 空間：O(n²)。

總結

POJ 1050 是二維最大子矩陣和的標準模板題。核心技巧：固定上下行邊界 → 列前綴和 → 一維最大子段和。此 O(n³) 算法在 N≤100 時為最優解法。掌握此模板，所有「連續子矩陣極值」問題（最大和、最小和、最大平均值等）均可類比求解。