概要

与えられた数列から、合計が \(0\) 以上となる連続部分列のうち、合計の最大値を求める問題です。空の部分列も選べるとされ、その合計は \(0\) とします。

考察

この問題は、いわゆる「最大部分列和問題（Maximum Subarray Problem）」の亜種です。通常の最大部分列和問題では、連続する部分列の和の最大値を求めますが、本問題では「和が負にならない」という制限があります。しかし、実はこの制限はアルゴリズム的に自然に扱うことができ、和が負になったら部分列の選択をリセットするという考え方が有効です。

素朴な方法として、全ての \(l, r\) の組み合わせを試すことが考えられますが、これは \(O(N^2)\) かかり、\(N\) が最大 \(2 \times 10^5\) なので現実的ではありません（TLEになります）。そこで、線形時間で解けるアルゴリズムを考える必要があります。

ここで注目すべきは、左端を固定せず、右端を順に見ていきながら、現在の連続和を管理することです。もし途中で和が負になったら、それ以前の部分列は今後の候補から外しても良い（リセットして良い）というアイデアが重要です。このようにして、常に「今見ている位置を右端とする最適な部分列」を効率良く管理できます。

アルゴリズム

この問題には、Kadane’s Algorithm（カダネのアルゴリズム）と呼ばれる有名なアルゴリズムが適用できます。

アルゴリズムの流れは以下の通りです： 1. current_sum：現在の連続部分列の和（ただし負にならないように管理する） 2. max_sum：これまでに見た中での最大の和（初期値は \(0\)）

配列を左から右へ走査しながら以下を行う： - current_sum に現在の要素を加える - もし current_sum が負になったら、current_sum = 0 としてリセット（つまり新しい部分列をここから始める） - max_sum を current_sum の最大値で更新する

このようにすることで、線形時間で最大和を求めることができます。

例

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

i	A[i]	current_sum	max_sum
0	-2	0	0
1	1	1	1
2	-3	0	1
3	4	4	4
4	-1	3	4
5	2	5	5
6	1	6	6
7	-5	1	6
8	4	5	6

最終的な答えは \(6\) となります。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• current_sum は負にならないように管理する（負になったら \(0\) に戻す）

• 最初の max_sum は \(0\) で初期化（空の部分列を選んでも良いので）

• 各要素に対して一度だけ処理を行うため、非常に高速に動作する

  ソースコード

N = int(input())
A = list(map(int, input().split()))

max_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)

---

この解説は qwen3-coder-480b によって生成されました。