메뉴 건너뛰기

문제

00b00 연속부분 최대합   0  

시간메모리제출 올바른 답 비율
1초64MB
3462
452
13.1%


나의 횟수나의 최근 판정시도 성공 비율
389300
77.1%
연속부분 최대합 

일차원 배열에 n개의 정수가 담겨 있다. 배열에서 임의의 연속된 구간을 잡아 그 합이 최대가 되도록 하려고 한다. 예를 들어 다음과 같은 일차원 배열이 주어질 때,

1 -3 4 -2 8 -9 3 3 2 -1 

다음과 같이 연속된 구간을 선택하면 그 합이 10이 되고

1 -3 4 -2 8 -9 3 3 2 -1 

다음과 같이 연속된 구간을 선택하면 그 합이 8이 된다.

1 -3 4 -2 8 -9 3 3 2 -1 

n과 n개의 수를 입력받아 합이 최대가 되도록 하는 연속구간을 찾아 그 합을 출력하는 효율적인 프로그램을 작성하시오.

입력

첫째 줄에 1,000,000 이하의 자연수 n이 주어진다. 둘째 줄에는 일차원 배열에 담겨 잇는 n개의 정수가 차례로 주어진다. 일차원 배열에 담긴 정수는 –100이상, 100이하이다.

출력

첫째 줄부터 연속된 구간의 합 중 최대값을 출력한다.

예시
1입력
10
1 –3 4 –2 8 –9 3 3 2 -1
출력
10
위로