Day 085-Q2 — 最大部分矩形和（2D Kadane・$O(H^2 W)$）

問題

$H \times W$ の整数行列 $A$（負値を含む）が与えられる。行列内の空でない部分矩形（連続行区間 $\times$ 連続列区間）の要素和のうち、最大値を求めよ。

入出力例

4 4
1 -2 3 4
-5 6 -1 2
2 -3 4 -1
1 2 -6 3

12

概念図: 行ペア固定 → 縦和列 → 1D Kadane

ヒント

for t in range(H):
    col = [0]*W
    for b in range(t, H):
        for j in range(W):
            col[j] += A[b][j]   # 下端行を差分追加
        cur = best = col[0]     # 1D Kadane（空不可）
        for j in range(1, W):
            cur = col[j] if cur < 0 else cur + col[j]
            best = max(best, cur)
        ans = max(ans, best)

模範解答

import sys
input = sys.stdin.readline

def solve():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]

    ans = float('-inf')
    for t in range(H):
        col = [0] * W
        for b in range(t, H):
            rowB = A[b]
            for j in range(W):
                col[j] += rowB[j]
            cur = col[0]
            best = col[0]
            for j in range(1, W):
                cj = col[j]
                cur = cj if cur < 0 else cur + cj
                if cur > best:
                    best = cur
            if best > ans:
                ans = best
    print(ans)

solve()

計算量: $O(H^2 W)$ 時間、$O(W)$ 追加空間。

Step-by-Step 解説

Step 1: 問題の分解

部分矩形 = 行区間 $[t,b]$ × 列区間 $[l,r]$。行区間を全探索すれば、残りは各列縦和からなる1次元列の最大部分和に帰着。

Step 2: 縦和の差分更新

Step 3: Kadane（空を許さない版）

cur = c if cur < 0 else cur + c は「これまでの和が負なら捨てて単独再スタート」。初期値を配列先頭にするため負値のみでも最大単一要素を返す。

Step 4: 計算量

$O(H^2 W) = 500^2 \times 500 = 1.25\times10^8$。内側ループを最小演算に絞れば通る（CPython なら numpy 化も有効）。

よくあるミス

次のステップ

• 発展問題: 面積制約付き最大和矩形（辺長 $\ge k$ 制約）
• 発展問題: 最大和矩形を numpy / prefix sum で定数倍高速化

自己評価