分割統治法 (Divide & Conquer) を用いた最大部分配列の合計

整数が n 個含まれる配列が与えられたときに、分割統治法を使って連続する部分配列の中から合計値が最大となるものを見つけます。

入力

入力の最初の行には、配列の要素数を示す整数 n が与えられます (1 ≤ n ≤ )。

次の行には、配列の要素を表す n 個の整数がスペース区切りで与えられます ()。

出力

プログラムは、与えられた配列の部分配列のうち、取得できる最大の合計値を表す整数を1つ出力します。

例

解説

1. -2 1 -3 4 -1 3 1 -4 -2 → ハイライトされた部分配列の合計は (4 - 1 + 3 + 1) = 7

2. 1 -2 3 4 -3 1 7 -10 -20 4 → 3 + 4 -3 + 1 + 7 = 12