概要

数列から連続する部分列を選び、その合計の最大値を求める問題です。空の部分列（合計 \(0\)）も許されるため、答えは必ず \(0\) 以上になります。

考察

重要な気づき

• 連続部分列の選び方は \(O(N^2)\) 通りあります（始点 \(l\) と終点 \(r\) の組み合わせ）
• 空の部分列が許されるので、全ての要素が負でも答えは \(0\) になります

素朴なアプローチの問題点

全ての \((l, r)\) の組み合わせを試し、それぞれの合計を計算すると： - 組み合わせ: \(O(N^2)\) 通り - 各合計の計算: \(O(N)\) - 合計: \(O(N^3)\)

累積和を使っても \(O(N^2)\) となり、\(N = 2 \times 10^5\) では TLE になります。

解決の鍵

Kadane’s Algorithm（カデインのアルゴリズム） を使うことで、\(O(N)\) で解けます。

このアルゴリズムの核心は：

「位置 \(i\) で終わる連続部分列の最大和」を効率的に更新していく

という考え方です。

アルゴリズム

Kadane’s Algorithm の仕組み

変数の意味： - current_sum: 現在位置で終わる連続部分列の最大和 - max_sum: これまでに見つけた最大和

各位置 \(i\) で以下の選択を行います： 1. 前の部分列に \(A_i\) を追加する: current_sum + A[i] 2. \(A_i\) から新しく始める: \(A_i\)（つまり前の部分列を捨てる） 3. 空の部分列を選ぶ: \(0\)

これを current_sum = max(0, current_sum + A[i]) で表現しています。

具体例

数列 \(A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]\) の場合：

\(i\)	\(A_i\)	current_sum の更新	max_sum
0	-2	max(0, 0+(-2)) = 0	0
1	1	max(0, 0+1) = 1	1
2	-3	max(0, 1+(-3)) = 0	1
3	4	max(0, 0+4) = 4	4
4	-1	max(0, 4+(-1)) = 3	4
5	2	max(0, 3+2) = 5	5
6	1	max(0, 5+1) = 6	6
7	-5	max(0, 6+(-5)) = 1	6
8	4	max(0, 1+4) = 5	6

答えは \(6\)（部分列 \([4, -1, 2, 1]\)）

なぜこれで正しいのか

• current_sum が負になりそうなとき、\(0\) にリセットする = 空の部分列から再スタート
• 過去の最大値は max_sum で記録しているので、リセットしても問題なし
• 全ての位置で「その位置で終わる最大和」を考慮しているので、最適解を見逃さない

計算量

• 時間計算量: \(O(N)\)（配列を1回走査するだけ）
• 空間計算量: \(O(N)\)（入力配列の格納。変数のみなら \(O(1)\)）

実装のポイント

• max_sum と current_sum の初期値を \(0\) にすることで、空の部分列（合計 \(0\)）を自然に扱える

• オーバーフローに注意：最大で \(N \times 10^9 = 2 \times 10^{14}\) になりうるが、Python では整数のオーバーフローがないので安心

  ソースコード

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    # Kadane's algorithm to find maximum subarray sum
    # We also allow empty subarray (sum = 0)
    
    max_sum = 0  # Empty subarray has sum 0
    current_sum = 0
    
    for i in range(N):
        current_sum = max(0, current_sum + A[i])
        max_sum = max(max_sum, current_sum)
    
    print(max_sum)

solve()

---

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