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

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

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

 
n과 n개의 수를 입력받아 합이 최대가 되도록 하는 연속구간을 찾아 그 합을 출력하는 효율적인 프로그램을 작성하시오. 실행 파일의 이름은 문제 코드와 동일하다. 실행 시간은 1초를 넘을 수 없다.
 
입력 형식
입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 1,000,000 이하의 자연수 n이 주어진다. 둘째 줄에는 일차원 배열에 담겨 잇는 n개의 정수가 차례로 주어진다. 일차원 배열에 담긴 정수는 –100이상, 100이하이다.
 
출력 형식
출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄부터 연속된 구간의 합 중 최대값을 출력한다.
 
 
입력과 출력의 예
입력 (INPUT.TXT)

출력 (OUTPUT.TXT)

 
 
// 연속부분최대합 O(n^3) 알고리즘
 
#include <stdio.h>
#define MAX(x,y) (((x)>(y))?(x):(y))
 
int a[1000000];
 
int main()
{
int i,j,k,n;
int sum=0;
int max=-9999;
 
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
 
 
for(i=0;i<n;i++){
for(j=i;j<n;j++){
sum=0;
for(k=i;k<=j;k++){
sum+=a[k];
}
max=MAX(max,sum);
}
}
printf("%d",max);
 
return 0;
}