[백준] 1912번 연속합

문제 링크

 

풀이

점화식 d[i]는 i번째 요소까지의 연속합의 최대 값입니다. 문제에서 수는 한 개 이상 선택해야 한다고 했으므로 d[i-1]번째 수와 arr[i]를 더했을 때의 값이 arr[i]의 값보다 작다면 i번째 요소인 arr[i] 자체가 연속합의 최대 값이 됩니다. 그러므로 다음과 같은 점화식을 세울 수 있습니다. answer의 초기 값이 -100000000인 이유는 요소에 음수 값이 있을 수 있기 때문입니다.

 

d[i] = max(d[i-1] + arr[i], arr[i])

 

코드

#include <cstdio>
int max(int a, int b)
{
	return a > b ? a : b;
}
int main()
{
	int N;
	scanf("%d", &N);
	int d[100001] = {};
	int arr[100001] = {};
	int answer = -100000000;
	for (int i = 1; i <= N; ++i)
	{
		scanf("%d", &arr[i]);
		d[i] = max(d[i - 1] + arr[i], arr[i]);
		answer = max(d[i], answer);
	}
	printf("%d", answer);
}