제목.

최대 연속 서열의 합을 구하다

규칙 및 범위 입력

첫 번째 줄은 n(n<=500)을 입력하고, 두 번째 행위는 n개의 공백으로 나누는 정수(-100에서 1000 사이)를 입력한다.

샘플 가져오기

６
1 2 -5 6 7 8

출력 예제

21

문제풀이의 방향

먼저 모든 기점, 임의의 종점의 최대 연속 수열의 합을 구하고 비교한 다음에 가장 큰 것을 구하는 것이 바로 답이다.

코드

#include
#include
using namespace std;
int n,a[501],ans=0,f[501];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	f[1]=a[1];//   
	for (int i=1;i<=n;i++)
	{
	 f[i]=f[i-1]+a[i];//                 
	 if (f[i]<0) f[i]=0;//       <0，    0，    
	 ans=max(f[i],ans);//          
	}
	printf("%d",ans);
	return 0;
}