| 연속부분 최대합 |
|---|
일차원 배열에 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 | ||