G - Range Sum Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

長さ N の整数列 A = (A_1, A_2, \ldots, A_N) が与えられます。

1 \leq l \leq r \leq N を満たす整数の組 (l, r) を任意に選ぶときの、 A_l + A_{l+1} + \cdots + A_r の値としてあり得る最大値を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

10
-6 5 -3 3 -1 4 -1 5 -9 2

出力例 1

12

(l, r) = (2, 8) のとき、A_2 + A_3 + \cdots + A_8 = 5 + (-3) + 3 + (-1) + 4 + (-1) + 5 = 12 であり、これが最大です。

入力例 2

3
-1 -2 -3

出力例 2

-1

入力例 3

20
-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16

出力例 3

176

Problem Statement

You are given an integer sequence of length N: A = (A_1, A_2, \ldots, A_N).

Print the maximum possible value of A_l + A_{l+1} + \cdots + A_r for a pair (l, r) such that 1 \leq l \leq r \leq N.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq A_i \leq 10^9
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

10
-6 5 -3 3 -1 4 -1 5 -9 2

Sample Output 1

12

For (l, r) = (2, 8), we have A_2 + A_3 + \cdots + A_8 = 5 + (-3) + 3 + (-1) + 4 + (-1) + 5 = 12, which is the maximum possible value.

Sample Input 2

3
-1 -2 -3

Sample Output 2

-1

Sample Input 3

20
-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16

Sample Output 3

176