POJ 1050 To the MAX：二維最大子矩陣和

題意

給定 N×N 矩陣 (N ≤ 100)，找出一個子矩陣使其元素和最大。

思路

將二維問題降維為一維。枚舉上邊界 top 和下邊界 bottom，將這兩行之間的每列元素累加到暫存陣列 tmp 中，然後在 tmp 上求最大連續子數組和（Kadane 算法）。遍歷所有 top、bottom 組合，取最大值即為答案。時間複雜度 O(N^3)。

代碼 (C++)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 1e9;
const int MAXN = 110;
int n, mat[MAXN][MAXN], tmp[MAXN];

int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &mat[i][j]);
        int ans = -INF;
        for (int top = 0; top < n; top++) {
            memset(tmp, 0, sizeof(tmp));
            for (int bottom = top; bottom < n; bottom++) {
                for (int col = 0; col < n; col++)
                    tmp[col] += mat[bottom][col];
                // Kadane 算法求 tmp 最大連續和
                int cur = tmp[0], best = tmp[0];
                for (int i = 1; i < n; i++) {
                    cur = max(tmp[i], cur + tmp[i]);
                    best = max(best, cur);
                }
                ans = max(ans, best);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}