概要

この問題は、与えられた2次元グリッドから要素の和が最大となる長方形領域を見つける最大部分長方形和問題です。

考察

素朴なアプローチでは、全ての可能な長方形領域（左上と右下の座標の組み合わせ）を試すと、\(O(N^2M^2)\) の時間計算量となり、制約 \(N, M \leq 500\) では最大で約 \(500^4 = 62,500,000,000\) 回の計算が必要になり、現実的ではありません。

重要な観察は、行方向の範囲を固定したとき、列方向については1次元配列の最大部分和問題に帰着できることです。行範囲 \([top, bottom]\) を固定すると、各列の和を計算することで、その行範囲内での列方向の累積和を1次元配列として扱えます。この1次元配列に対して Kadaneのアルゴリズム を用いることで、\(O(M)\) で最大部分和を求めることができます。

アルゴリズム

1. 上端行 \(top\) を \(0\) から \(N-1\) までループ
2. 各 \(top\) について、下端行 \(bottom\) を \(top\) から \(N-1\) までループ
3. 各行範囲 \([top, bottom]\) について、各列の和を保持する配列 \(temp\) を更新（\(bottom\) が1つ下がるごとに、対応する行の値を \(temp\) に加算）
4. 更新された \(temp\) 配列に対して、Kadaneのアルゴリズムを適用して最大部分和を計算
   • \(current = \max(num, current + num)\) で現在の部分和を更新
   • \(best = \max(best, current)\) で全体の最大値を更新
5. 全ての行範囲について得られた最大部分和の最大値を答えとする

計算量

• 時間計算量: \(O(N^2M)\)
  • 外側の2重ループが \(O(N^2)\)、内側のKadaneのアルゴリズムが \(O(M)\)
• 空間計算量: \(O(M)\)
  • 列方向の和を保持する配列 \(temp\) のサイズが \(M\)

実装のポイント

• 各行範囲を固定するごとに、列方向の累積和を効率的に計算するために、\(temp\) 配列を再利用しています

• Kadaneのアルゴリズムを適用する際、初期値の \(current\) と \(best\) を十分に小さい負の値に設定することで、全ての要素が負の場合でも正しく動作します

• 入力値の範囲に注意し、\(ans\) の初期値を \(-10^{18}\) など十分に小さい値に設定しています

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    grid = []
    for i in range(n):
        row = []
        for j in range(m):
            row.append(int(next(it)))
        grid.append(row)
    
    ans = -10**18
    for top in range(n):
        temp = [0] * m
        for bottom in range(top, n):
            for col in range(m):
                temp[col] += grid[bottom][col]
            current = 0
            best = -10**18
            for num in temp:
                current = max(num, current + num)
                best = max(best, current)
            ans = max(ans, best)
    
    print(ans)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。