BOJ [1912] 연속합

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

1. 분류

다이나믹 프로그래밍

2. 풀이

숫자를 여러 개 주고 연속된 숫자들의 합 중 가장 큰 값을 도출해내는 문제이다.

다이나믹 프로그래밍으로 해결했다.

첫 숫자부터 끝 숫자까지 순회면서 (dp+현재 값)과 현재값 중 큰 값을 남긴다.

그리고 다시 처음부터 최고값을 찾는다.

3. 소스코드

#include <cstdio>
#define max(a, b) (a) > (b) ? (a) : (b)

int num[100000];
int dp[100000];

int main()
{
	int n, ans;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
		scanf("%d", &num[i]);

	dp[0] = num[0];
	ans = dp[0];

	for (int i = 1; i < n; i++)
		dp[i] = max(dp[i - 1] + num[i], num[i]);

	for (int i = 0; i < n; i++)
		ans = max(ans, dp[i]);

	printf("%d\n", ans);
	return 0;
}