問題定義

給定二維矩陣/三維立方體，找出子矩陣/子長方體元素和的最大值。元素可正可負。

一維基礎：最大子數組和 (Kadane)

int maxSubArray(const std::vector<int>& a) {
    int cur = a[0], best = a[0];
    for (size_t i = 1; i < a.size(); ++i) {
        cur = std::max(a[i], cur + a[i]);
        best = std::max(best, cur);
    }
    return best;
}

時間 O(n)，空間 O(1)。核心：以 i 結尾的最大和 = max(單獨 a[i], 延續前序列)。

二維矩陣：三種方案遞進

方案一：暴力枚舉 O(n²m² × n) = O(n³m²) 或 O(n²m³)

枚舉所有頂點對 (r1,c1)-(r2,c2)，雙循環求和。極慢。

方案二：二維前綴和 + 枚舉邊界 O(n²m²)

預計算 sum[i][j] = 左上角 (1,1) 到 (i,j) 矩形和。任意子矩陣和 O(1) 獲取：

sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1]

仍需枚舉四個邊界，O(n²m²)。

方案三：降維 + Kadane O(n²m) —— 工程首選

核心洞察：固定上下行邊界 top, bottom，將每列在該行範圍內的和視為一維數組元素，問題轉化為一維最大子數組和。

int maxSubMatrix(const std::vector<std::vector<int>>>& mat) {
    int rows = mat.size(), cols = mat[0].size();
    // 列前綴和：colSum[r+1][c] = 前 r 行第 c 列和
    std::vector<std::vector<int>> colSum(rows+1, std::vector<int>(cols));
    for (int r = 0; r < rows; ++r)
        for (int c = 0; c < cols; ++c)
            colSum[r+1][c] = colSum[r][c] + mat[r][c];

    int best = mat[0][0];
    for (int top = 0; top < rows; ++top) {
        for (int bottom = top; bottom < rows; ++bottom) {
            // 構建一維數組
            std::vector<int> arr(cols);
            for (int c = 0; c < cols; ++c)
                arr[c] = colSum[bottom+1][c] - colSum[top][c];
            // Kadane
            int cur = arr[0];
            best = std::max(best, cur);
            for (int c = 1; c < cols; ++c) {
                cur = std::max(arr[c], cur + arr[c]);
                best = std::max(best, cur);
            }
        }
    }
    return best;
}

時間：O(rows² × cols)。若 rows > cols，可轉置矩陣優化。

環形矩陣擴展（行/列首尾相連）

對於列環形：在 Kadane 基礎上，計算總和，用「總和 - 最小子數組和」處理跨邊界情況（需排除全選情況）。行環形同理枚舉行範圍時處理跨邊界。

三維長方體：降維至二維 O(n⁵)

固定前後兩個面 front, back，將中間層壓縮為二維矩陣，套用二維方案三。

int maxSubCube(const std::vector<std::vector<std::vector<int>>>& cube) {
    int X = cube.size(), Y = cube[0].size(), Z = cube[0][0].size();
    // 前綴和：pre[x+1][y][z] = 前 x 層 (y,z) 和
    std::vector pre(X+1, std::vector(Y, std::vector(Z, 0)));
    for (int x = 0; x < X; ++x)
        for (int y = 0; y < Y; ++y)
            for (int z = 0; z < Z; ++z)
                pre[x+1][y][z] = pre[x][y][z] + cube[x][y][z];

    int best = cube[0][0][0];
    for (int front = 0; front < X; ++front) {
        for (int back = front; back < X; ++back) {
            // 壓縮為二維矩陣
            std::vector mat(Y, std::vector(Z));
            for (int y = 0; y < Y; ++y)
                for (int z = 0; z < Z; ++z)
                    mat[y][z] = pre[back+1][y][z] - pre[front][y][z];
            // 套用二維最大子矩陣
            best = std::max(best, maxSubMatrix(mat));
        }
    }
    return best;
}

時間：O(X² × Y² × Z) = O(n⁵)。空間：O(XYZ)。

複雜度總結

工程優化

• 使用 long long 防溢出
• 行列較大時選擇較小維度作外層枚舉
• 矩陣稀疏時可優化存儲
• 並行化外層枚舉循環（OpenMP/TBB）