UVA 10755 三維最大子陣列和 詳解

題目：給定 A×B×C 的長方體，每個單元格有權值（可正可負）。求一個子長方體，使其權值和最大。A,B,C ≤ 20（實際測試中可能更大，需 O(n³) 以上算法）。

核心思想：降維 + 最大子段和

二維最大子矩陣和經典做法：枚舉上下邊界，將列壓縮為一維陣列，跑 Kadane 算法（最大子段和）。
三維同理：枚舉前後邊界（Z 軸），將中間層疊加為二維矩陣，再轉化為二維問題。

具體步驟

1. 預處理前綴和：sum[z][x][y] 表示第 z 層從 (1,1) 到 (x,y) 的矩形和。可在 O(1) 計算任意層任意子矩形和。
2. 枚舉 Z 軸區間：startZ 從 1 到 C，endZ 從 startZ 到 C。維護一個二維陣列 layer[x][y]，累加 startZ..endZ 每層的值。
3. 二維轉一維：對累加後的 layer，枚舉行區間 startX, endX，將列壓縮為一維陣列 col[y]。
4. 一維最大子段和：對 col 跑 Kadane，得到當前 Z/X 區間下的最大和，更新全局答案。

優化：直接三維前綴和 + 四重循環枚舉

由於 A,B,C ≤ 20（較小），可直接用三維前綴和 G[x][y][z] 表示 (1,1,1) 到 (x,y,z) 的和。枚舉所有子長方體的 6 個面邊界（x1,x2,y1,y2,z1,z2），O(1) 計算體積和。總複雜度 O(A²B²C²)，對於 20³ 約 6400 萬次，配合優化可通過。

更優做法：枚舉 X,Y 區間，Z 軸跑最大子段和（如原文代碼），複雜度 O(A²B²C) 或 O(A²C²B) 等，取最小維度作為內層掃描。

原文代碼邏輯解析 (C++)

// g[x][y][z] 為第 z 層 (1,1) 到 (x,y) 的二維前綴和
// 枚舉 x1,x2,y1,y2 確定 X,Y 範圍
// 對 Z 軸掃描：維護滑動窗口 [startZ, endZ]，累加當前層在該 X,Y 範圍的和
// 若累加和 < 0，移動 startZ 縮小窗口（同 Kadane 邏輯）
// 更新全局最大值 ans

關鍵代碼片段

ll sum(int x1, int x2, int y1, int y2, int z) {
    return g[x2][y2][z] - g[x1-1][y2][z] - g[x2][y1-1][z] + g[x1-1][y1-1][z];
}

for (int x1=1; x1<=A; ++x1)
  for (int x2=x1; x2<=A; ++x2)
    for (int y1=1; y1<=B; ++y1)
      for (int y2=y1; y2<=B; ++y2) {
          int sz = 1;
          ll cur = 0;
          for (int ez=1; ez<=C; ++ez) {
              cur += sum(x1,x2,y1,y2,ez);
              ans = max(ans, cur);
              while (cur < 0 && sz <= ez) {
                  cur -= sum(x1,x2,y1,y2,sz);
                  ++sz;
                  if (sz <= ez) ans = max(ans, cur);
              }
          }
      }

複雜度分析

關鍵點總結

1. 降維打擊：高維最大子陣列問題，核心是將維度逐步降低，最終歸結為一維最大子段和（Kadane）。
2. 前綴和加速：任意子矩形/子長方體和 O(1) 查詢是基礎。
3. 負值處理：Kadane 算法的精髓在於「和變負則重置」，三維同理。
4. 枚舉順序選擇：將最小維度放在最內層掃描，可顯著降低常數因子。

總結

UVA 10755 是「多維最大子陣列和」的經典入門題。它完美展示了從一維 Kadane → 二維枚舉邊界+Kadane → 三維再枚舉一維的推廣路徑。掌握此模式，可解決 LeetCode 363、560 等變體，以及更高維度的類似問題（如四維掃描）。工程上，若維度較大（>100），需考慮隨機化、近似算法或稀疏表示。