10079 최대 구간 합 Silver III

문제

N개의 정수로 이루어진 수열에서 연속된 부분수열의 합 중 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에 N개의 정수가 주어진다. 각 정수는 절댓값이 1,000 이하이다.

출력

최대 구간 합을 출력한다.

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

9