/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 333 点
問題文
高橋君は、ある数列の分析を行っています。
N 個の整数からなる数列 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 つも選ばないこと（空の区間を選ぶこと）も許されており、その場合の合計は 0 とします。
これらすべての選び方における合計の最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N A_1 A_2 \cdots A_N
- 1 行目には、数列の要素数を表す整数 N が与えられる。
- 2 行目には、数列の各要素を表す整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
連続する区間の合計（空の区間の場合は 0）の最大値を 1 行で出力せよ。
入力例 1
5 3 -1 4 -2 2
出力例 1
6
入力例 2
8 -2 1 -3 4 -1 2 1 -5
出力例 2
6
入力例 3
10 -5 -3 -1 -2 -4 -6 -1 -8 -2 -7
出力例 3
0
Score : 333 pts
Problem Statement
Takahashi is analyzing a certain sequence.
He is given a sequence of N integers A_1, A_2, \ldots, A_N. Takahashi wants to select a contiguous subarray from this sequence such that the sum of its elements is maximized.
Specifically, he chooses a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N, and computes the subarray sum A_l + A_{l+1} + \cdots + A_r.
It is also permitted to select no elements (i.e., to choose an empty subarray), in which case the sum is defined to be 0.
Find the maximum sum among all possible choices.
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq A_i \leq 10^9
- All input values are integers.
Input
N A_1 A_2 \cdots A_N
- The first line contains an integer N, representing the number of elements in the sequence.
- The second line contains the integers A_1, A_2, \ldots, A_N, representing the elements of the sequence, separated by spaces.
Output
Print the maximum sum of a contiguous subarray (or 0 in the case of an empty subarray) on a single line.
Sample Input 1
5 3 -1 4 -2 2
Sample Output 1
6
Sample Input 2
8 -2 1 -3 4 -1 2 1 -5
Sample Output 2
6
Sample Input 3
10 -5 -3 -1 -2 -4 -6 -1 -8 -2 -7
Sample Output 3
0