部分配列の和の最大値

整数列 A1, A2, …, AN が与えられます。
このとき、連続する部分配列のうち 和が最大となる値を求めてください。

入力

N
A1 A2 ... AN

• 1 行目に整数 N (1 ≤ N ≤ 1000)
• 2 行目に N 個の整数 Ai (−10^4 ≤ Ai ≤ 10^4)

出力

部分配列の和の最大値を出力せよ。

入力例1

5
1 -2 3 4 -1

出力例1

7

（部分配列 [3,4] の和が最大で 7）

入力例2

4
-5 -2 -3 -4

出力例2

-2

（最大でも -2。空配列は不可とする）

入力例3

6
2 -1 2 -1 2 -1

出力例3

4

（部分配列 [2, -1, 2, -1, 2] の和が最大で 4）

ポイント

• 素直に 2 重ループで部分配列を調べても O(N^2) で解ける。
• 発展的には Kadane’s algorithm を使えば O(N) で解ける。
• 実務や競技でもよく出る「最大部分和問題」の入門版。

ケン

ヨワモンのパートナー

ヨワモンのパートナー