최대 연속 부분합

정수 n개로 이루어진 수열이 주어진다. 이 수열에서 하나 이상의 연속한 원소를 선택했을 때 만들 수 있는 합의 최댓값을 구하라.

첫째 줄에 정수 n (1 ≤ n ≤ 100,000)이 주어진다.

둘째 줄에는 n개의 정수가 공백으로 구분되어 주어진다. 각 정수는 -1,000 이상 1,000 이하이다.

하나 이상의 연속한 원소를 선택해 얻을 수 있는 합의 최댓값을 출력한다.