概要

\(N \times M\) の整数グリッドから「1つ以上のマスを含む長方形」を選び、その総和を最大化する問題です。
2次元の最大部分和問題（最大長方形部分和）を高速に解きます。

考察

重要な気づき

長方形は「上端 \(top\)・下端 \(bottom\) を固定すると、各列ごとの合計」に圧縮できます。

例えば \(top=2, bottom=4\) を固定すると、列 \(j\) について [ Bj = \sum{i=top}^{bottom} A_{i,j} ] という1次元配列 \(B\) が作れます。このとき、列範囲 \([c_1, c_2]\) の長方形の和は [ \sum_{j=c_1}^{c_2} B_j ] となり、「1次元配列の最大連続部分和（最大部分配列和）」に帰着します。

素朴解が遅い理由

長方形は \((r_1,r_2,c_1,c_2)\) の4つを選ぶので個数は \(O(N^2 M^2)\)。
各長方形の和を計算するとさらに重くなり、\(N,M \le 500\) では到底間に合いません。

解決方針

• 行のペア \((top,bottom)\) を全探索（または列のペア \((left,right)\) を全探索）
• その都度、もう一方の次元に圧縮した1次元配列にして
• Kadane法（最大部分配列和）で最大値を更新

さらに、\(N\) と \(M\) のうち小さい方を「ペア全探索する次元」に選ぶと計算量が最小になります（コードでも分岐しています）。

アルゴリズム

以下では \(N \le M\) の場合（行ペアを固定）を説明します。\(N > M\) の場合は行と列を入れ替えた同様の処理です。

1. 答え ans を十分小さい値（負の無限大）で初期化する
   ※空の長方形は選べないので、全要素が負でも最大（=最もマシな負）を必ず選ぶ必要があります。
2. 上端 top を \(0..N-1\) で動かす
3. temp[j] を「列 \(j\) の \(top..bottom\) の縦方向合計」として 0 で初期化
4. 下端 bottom を top..N-1 で動かす
   
   • temp[j] += A[bottom][j] と更新して、\(top..bottom\) の圧縮配列を得る
   • temp に対して Kadane法を実行し、最大連続部分和を ans に反映する

Kadane法（1次元最大部分和）は次で求まります： - cur を「今見ている位置で終わる最大部分和」とする - 次の値 v に対し [ cur = \max(v,\ cur+v) ] - 各ステップで ans = max(ans, cur) と更新

コードでは高速化のために if cur > 0: cur += v else: cur = v という形で同じことをしています。

計算量

小さい方を \(K=\min(N,M)\)、大きい方を \(L=\max(N,M)\) とすると、

• 時間計算量: \(O(K^2 \cdot L)\)
  （ペアが \(O(K^2)\) 個、各ペアで Kadane が \(O(L)\)）
• 空間計算量: \(O(L)\)
  （圧縮用配列 temp のみ）

実装のポイント

• 次元の入れ替え（分岐）：\(N \le M\) なら行ペア、そうでなければ列ペアを固定して \(O(\min(N,M)^2 \max(N,M))\) に抑えます。

• 全負対策：ans を非常に小さい値で初期化し、Kadane の更新で必ず1要素以上を選ぶ形にしています（空選択を許さない）。

• 高速入出力：sys.stdin.buffer.read().split() を使って Python でも間に合わせやすくしています。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    vals = list(map(int, data))
    N, M = vals[0], vals[1]
    idx = 2
    A = [vals[idx + i*M: idx + (i+1)*M] for i in range(N)]

    NEG_INF = -10**30
    ans = NEG_INF

    if N <= M:
        C = M
        for top in range(N):
            temp = [0] * C
            for bottom in range(top, N):
                row = A[bottom]
                t = temp
                cur = 0
                for j in range(C):
                    v = t[j] + row[j]
                    t[j] = v
                    if cur > 0:
                        cur += v
                    else:
                        cur = v
                    if cur > ans:
                        ans = cur
    else:
        R = N
        for left in range(M):
            temp = [0] * R
            for right in range(left, M):
                t = temp
                cur = 0
                rr = right
                for i in range(R):
                    v = t[i] + A[i][rr]
                    t[i] = v
                    if cur > 0:
                        cur += v
                    else:
                        cur = v
                    if cur > ans:
                        ans = cur

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。