N개의 정수로 이루어진 수열 A가 주어진다.

이 수열의 비어있지 않은 연속된 일부분을 선택하여 그 합이 최대가 되도록 하는 프로그램을 작성하시오.

예를 들어, 수열이 [10, -7, 5, 20, -35, 25, 10] 일 때, 연속된 구간 [25, 10]을 선택하면 합이 35로 최대가 된다.

단, 구간은 반드시 하나 이상의 원소를 포함해야 한다.

입력

첫 번째 줄에 수열의 크기 N이 주어진다.

두 번째 줄에 N개의 정수 Ai가 공백으로 구분되어 주어진다.

출력

연속된 구간의 합 중 최댓값을 출력한다.

제약 조건

1 ≤ N ≤ 100

-1000 ≤ Ai ≤ 1000

First line \(N\) (\(1 \le N \le 100\)); second line \(N\) integers (\(-1000 \le A_i \le 1000\)).

Print the maximum contiguous-subarray sum.

riseoj 작성

출처 Online Judge > GoldOJ