4274 - 부분합

Time Limit: 1s Memory Limit: 128MB

Submissions: 375 Solved: 102
Description

N개의 숫자가 주어졌을때, 연속된 숫자(2개이상 가능)를 선택하여 구할 수 있는 합 중 가장 큰 합은 얼마일까?

Input

* Line 1 : 단일 정수 N (1≤N≤100,000)

* Line 2 : 공백으로 구분된 N개의 정수 

 

Output

연속된 숫자를 선택하여 구할 수 있는 합 중 가장 큰 합을 정수로 출력. (합은 INT의 범위를 넘지 않음)

Sample Input
10
-3 1 8 7 2 -20 15 30 -60 40
Sample Output
45