題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P1719 最大加权矩形

Problem Statement

題目簡述

給定一個 n×nn\times n 的整數矩陣，請找出元素總和最大的非空子矩形，輸出其最大總和。

Constraints

約束條件

  • 1≤n≤1201 \le n \le 120
  • 矩陣元素為整數（可為負），範圍 [−127,127][-127, 127]

思路：二維前綴和 + 壓縮成一維最大子陣列

題目要在所有子矩形中找最大總和。

若直接枚舉「上、下、左、右」四條邊界，需要枚舉 O(n4)\mathcal{O}(n^4) 個矩形；而計算矩形和的時間又是 O(n2)\mathcal{O}(n^2)（因為矩形最多包含 n2n^2 個元素），整體會是 O(n6)\mathcal{O}(n^6)，這在 n=120n=120 時是完全不可行的。

我們可以考慮對計算方式和枚舉方式分別進行優化。

方法一：二維前綴和 + 枚舉四邊界

首先從計算方式下手，透過預處理二維前綴和，可以把任意子矩形和的計算從 O(n2)\mathcal{O}(n^2) 降到 O(1)\mathcal{O}(1)。

sum(x1,x2,y1,y2)=s[x2][y2]−s[x1−1][y2]−s[x2][y1−1]+s[x1−1][y1−1]sum(x1,x2,y1,y2) = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

但仍須枚舉左上角與右下角（等價於枚舉四個邊界），整體仍然是 O(n4)\mathcal{O}(n^4)。

複雜度分析

  • 時間複雜度：O(n4)\mathcal{O}(n^4)
  • 空間複雜度：O(n2)\mathcal{O}(n^2)

方法二：枚舉上下界 + 一維最大子陣列（Kadane / 前綴最小值）

本題還能再往下優化：

核心轉換

先固定「上界」與「下界」，把這兩橫列(row)之間的每一直行(col)加總，會得到一個一維陣列；
任何在這兩橫列(row)之間的子矩形，就等價於這個一維陣列的一段連續子陣列。

也就是說：

  • 固定上下界後，問題變成 53. Maximum Subarray。
  • 再枚舉所有上下界（共有 O(n2)\mathcal{O}(n^2) 組），每組跑一次一維最大子陣列（O(n)\mathcal{O}(n)），總共 O(n3)\mathcal{O}(n^3)。

複雜度分析

  • 時間複雜度：O(n3)\mathcal{O}(n^3)
  • 空間複雜度：O(n2)\mathcal{O}(n^2)

Code

方法一：二維前綴和 + 枚舉四邊界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solve():
    n = int(input())
    grid = [list(map(int, input().split())) for _ in range(n)]

    s = [[0] * (n + 1) for _ in range(n + 1)]
    for i, row in enumerate(grid, start=1):
        for j, val in enumerate(row, start=1):
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + val

    ans = float("-inf")
    for x1 in range(1, n + 1):
        for y1 in range(1, n + 1):
            for x2 in range(x1, n + 1):
                for y2 in range(y1, n + 1):
                    ans = max(
                        ans,
                        s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1],
                    )
    print(ans)

if __name__ == "__main__":
    solve()

方法二：枚舉上下界 + 一維最大子陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solve():
    n = int(input())
    grid = [list(map(int, input().split())) for _ in range(n)]

    ans = float("-inf")
    for x1 in range(n):
        A = [0] * n
        for x2 in range(x1, n):
            for j in range(n):
                A[j] += grid[x2][j]
            # 53. Maximum Subarray
            s = mn = 0
            for x in A:
                s += x
                ans = max(ans, s - mn)
                mn = min(mn, s)
    print(ans)

if __name__ == "__main__":
    solve()