시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 28 7 5 50.000%

문제

수열 s = s1, s2, ..., sn의 점수는 Σi·si로 구할 수 있다.

수열 s의 연속된 부분 수열의 점수의 최대값을 구하는 프로그램을 작성하시오.

입력

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

둘째 줄에는 s1, s2, ..., sn이 주어진다. (|si| ≤ 107)

출력

첫째 줄에 수열 s의 연속된 부분 수열의 점수 중 최대값을 출력한다.

예제 입력

6
5 -1000 1 -3 7 -8

예제 출력

16

예제 입력 2

5
1000 1000 1001 1000 1000

예제 출력 2

15003

예제 입력 3

3
-60 -70 -80

예제 출력 3

0

힌트

출처