最大部分配列和 (Maximum sum subarray)
与えられた長さ
n の整数配列において、連続した部分配列の合計値が最大となるものを求めてください。入力
入力の最初の行には、配列の要素数を示す整数
n が与えられます (1 ≤ n ≤ 10^6)。次の行には、要素数
n の整数がスペース区切りで与えられます ( -10^9 < a_i < 10^9 )。出力
連続した部分配列の中で得られる最大の合計値を表す整数を1つ出力してください。
例
入力 | 出力 |
9
-2 1 -3 4 -1 3 1 -4 -2 | 7 |
10
1 -2 3 4 -3 1 7 -10 -20 4 | 12 |
説明
- -2 1 -3
4 -1 3 1-4 -2 → ハイライトされた部分配列の合計は (4 - 1 + 3 + 1) = 7
- 1 -2
3 4 -3 1 7-10 -20 4 → 3 + 4 -3 + 1 + 7 = 12
もっとシンプルに解ける方法は？ 😎
追加の配列を使わずに解くことも可能です。試してみませんか？
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB