[BOJ] 1912 연속합

https://www.acmicpc.net/problem/1912

1912번: 연속합

알고리즘: DP

 

시간복잡도: O(N)

---

접근:

1. 연속합의 최댓값 구하기

 

수열의 특정 부분을 봤을 때,

이 수가 최대 연속합의 일부가 될 가능성이 있다는 것을 알 수 있을까?

 

일단 수열의 수들을 계속 더해나가자... 만약에 수가 양수일 시, 이들을 계속 더하다보면 최댓값에 도달할 것이다.

하지만, 이 문제는 중간 중간에 음수들이 섞여있다.

따라서 계속 더해 나가다가 부분합이 0보다 작아지게 되면, 

차라리 다음 수 부터 새로 더해나가는게 이득이다. 

(달리 말하면, 새로 더해나가는 수열이 최대 연속합이 될 가능성이 있다.) 

 

 

이 아이디어를 DP로 구현할 수 있다.

 

주의) 

예제에도 있지만 수열의 구성하는 성분이 모두 음수이면

이 중에 최댓값을 골라주어야 한다.

 

#include<stdio.h>

int main()
{
	int n, i;
	int D[100001]={0,}, a;
	int max;
	
	scanf("%d",&n);
	scanf("%d",&a);
	D[0] = a;
	max = a;
	for (i = 1; i < n; i++)
	{
		scanf("%d",&a);
		if (D[i-1] < 0)
			D[i] = a;
		else
			D[i] = D[i-1] + a;
		if (max < D[i])
			max = D[i];
	}
	
	printf("%d", max);
	return 0;
}