概要

\(N \times M\) のグリッドから長方形領域を1つ選び、その中の値の合計を最大化する問題です。1次元の「最大部分配列和（Kadane’s algorithm）」を2次元に拡張することで効率的に解けます。

考察

素朴なアプローチ

長方形領域は \((r_1, r_2, c_1, c_2)\) の4つの値で決まります。全ての組み合わせを試すと \(O(N^2 M^2)\) 通りあり、さらに各長方形の合計を求めるのに \(O(NM)\) かかると、全体で \(O(N^3 M^3)\) となり到底間に合いません。累積和を使って各長方形の合計を \(O(1)\) にしても \(O(N^2 M^2)\) で、\(N = M = 500\) のとき約 \(6.25 \times 10^{10}\) 回の計算となり、これもTLEになります。

重要な気づき：1次元問題への帰着

ここで1次元の 最大部分配列和 を思い出しましょう。長さ \(M\) の配列が与えられたとき、連続する部分配列の和の最大値は Kadane’s algorithm で \(O(M)\) で求められます。

2次元の長方形は「行の範囲 \((r_1, r_2)\)」と「列の範囲 \((c_1, c_2)\)」で決まります。行の範囲 \((r_1, r_2)\) を固定すると、各列 \(j\) について \(r_1\) 行目から \(r_2\) 行目までの合計 \(\text{col\_sum}[j] = \sum_{i=r_1}^{r_2} A_{i,j}\) を計算できます。すると、列方向の最適な範囲 \((c_1, c_2)\) を選ぶ問題は、配列 \(\text{col\_sum}\) に対する1次元の最大部分配列和の問題に帰着します。

具体例

例えば以下の \(3 \times 4\) のグリッドで \(r_1 = 1, r_2 = 2\) を固定すると：

	列1	列2	列3	列4
行1	1	-3	5	2
行2	4	1	-2	3

\(\text{col\_sum} = [5, -2, 3, 5]\) となり、これに対してKadane’s algorithmを適用すると最大部分配列和 \(= 11\)（全体）が得られます。

アルゴリズム

1. 全ての行の開始位置 \(r_1 = 0, 1, \ldots, N-1\) について：
   • 長さ \(M\) の配列 \(\text{col\_sum}\) を \([0, 0, \ldots, 0]\) で初期化する。
   • \(r_2 = r_1, r_1+1, \ldots, N-1\) の順に：
     • 各列 \(j\) について \(\text{col\_sum}[j]\) に \(A[r_2][j]\) を加算する（行を1行追加）。
     • \(\text{col\_sum}\) に対して Kadane’s algorithm を実行し、最大部分配列和を求める。
     • 全体の答えを更新する。
2. 全ての \((r_1, r_2)\) の組を試した後、答えを出力する。

Kadane’s algorithm は、配列を左から順に見ながら「現在の部分配列和 \(\text{current}\)」を管理します。各要素で \(\text{current} = \max(a_j, \text{current} + a_j)\) と更新し、途中の最大値が答えです。

計算量

• 時間計算量: \(O(N^2 \times M)\)
  • 行のペア \((r_1, r_2)\) が \(O(N^2)\) 通り、各ペアに対してKadane’s algorithmが \(O(M)\)。
  • \(N = M = 500\) のとき約 \(6.25 \times 10^7\) 回で十分高速。
• 空間計算量: \(O(NM)\)（入力の格納） + \(O(M)\)（\(\text{col\_sum}\) 配列）

実装のポイント

• \(r_2\) を1つ増やすたびに \(\text{col\_sum}[j]\) に \(A[r_2][j]\) を足すことで、毎回ゼロから列の合計を計算し直す必要がなくなる（累積的に更新）。

• 答えの初期値は \(-\infty\) にする。全要素が負の場合でも、少なくとも1マスは選ぶ必要があるため、\(0\) で初期化してはいけない。

• Python では sys.stdin.read() でまとめて入力を読み込むことで、入力処理を高速化している。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    A = []
    for i in range(N):
        row = [int(input_data[idx + j]) for j in range(M)]
        idx += M
        A.append(row)
    
    # Prefix sum over rows for each column
    # For each pair of rows (r1, r2), compress into 1D array and apply Kadane's algorithm
    # O(N^2 * M)
    
    ans = float('-inf')
    
    for r1 in range(N):
        col_sum = [0] * M
        for r2 in range(r1, N):
            for j in range(M):
                col_sum[j] += A[r2][j]
            # Kadane's algorithm on col_sum
            current = col_sum[0]
            best = col_sum[0]
            for j in range(1, M):
                current = max(col_sum[j], current + col_sum[j])
                if current > best:
                    best = current
            if best > ans:
                ans = best
    
    print(ans)

main()

---

この解説は claude4.6opus-thinking によって生成されました。