最大部分配列和 (Maximum sum subarray)

与えられた長さ 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