HDU 1081 最大子矩陣問題：動態規劃與枚舉優化詳解

最大子矩陣問題深度解析

HDU 1081「最大子矩陣」是經典的二維動態規劃問題。其核心思想是將二維矩陣問題轉化為多個一維最大連續子序列和問題，通過「枚舉行 + 列向累加 + 一維 DP」的策略，在 O(n³) 時間複雜度內求解。

算法核心思路

1. 枚舉上下邊界：固定起始行 i，終止行 j (i ≤ j)，將第 i 到第 j 行的每一列累加，得到一個一維數組 mark[k]，代表該列在行區間內的總和。
2. 一維最大子序列和：對 mark 數組應用 Kadane 算法，求出最大連續子段和，即為以行 i 到 j 為上下邊界的最大子矩陣和。
3. 全局最大值：遍歷所有行對 (i, j)，記錄全局最大值。

關鍵代碼實現 (C++)

int linemax() { // 一維最大連續子序列和 (Kadane)
    int x = 0, Max = INF;
    for (int i = 1; i <= n; i++) {
        if (x > 0) x += mark[i];
        else x = mark[i];
        if (x > Max) Max = x;
    }
    return Max;
}

int rowmax() { // 枚舉行區間
    int Max = INF;
    for (int i = 1; i <= n; i++) { // 起始行
        memset(mark, 0, sizeof(mark));
        for (int j = i; j <= n; j++) { // 終止行
            for (int k = 1; k <= n; k++) 
                mark[k] += num[j][k]; // 列向累加
            int x = linemax();
            if (x > Max) Max = x;
        }
    }
    return Max;
}

複雜度分析與優化點

• 時間複雜度：O(n³)，n ≤ 100 時完全可接受。
• 空間複雜度：O(n²) 存儲矩陣，O(n) 輔助數組。
• 關鍵優化：利用 mark 數組原地累加，避免重複計算列和；Kadane 算法單次掃描即可得出一維最大值。

測試輸入輸出範例

輸入多組測試用例，每組先給 n，再給 n×n 矩陣，以 EOF 結束。程序對每組輸出最大子矩陣和。