연속합 (백준 - 1912번)

동적 계획법을 사용하여 해결하는 문제였다.

 

N번째에서 최대가 되는 연속합은 두가지 경우가 있다.

 

1. N-1번째의 연속합과 N번째 값을 더한 것

 

2. N번째 값 (N번째 부터 연속합을 구하는 경우)

 

이 두가지 경우를 점화식으로 만들면 다음과 같다.

 

N번째의 연속합을 기록할 DP테이블 배열 DP[N+1](인덱스 접근시 0부터 시작하므로)과 해당 번째의정수를 기록할 배열 num[N+1]이 있다고 했을때,

 

첫번째 경우는 DP[N] = DP[N-1] + num[N]이고, 두번째 경우는 DP[N] = num[N]이 된다.

 

이 둘중 가장 큰 값이 DP[N]에 알맞는 연속합 값이 된다. 1번째 부터 마지막 번째 까지 알맞는 DP값을 기록한 후 DP 배열 중 가장 큰 값이 이 문제의 결과값이 된다.

 

주의할 점은 음수가 있으므로 결과값이 음수가 될 수도 있다는 것이다. 그러므로 최대값을 계산할때 정수의 범위 (-1000 <= num <= 1000)를 숙지하고 있어야 한다.

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

int max(int a, int b)
{
	return (a > b) ? a : b;
}

int main()
{
	int input = 0;
	cin >> input;

	int* dp = new int[input + 1];
	int* num = new int[input + 1];

	dp[0] = 0;
	num[0] = 0;
	for (int i = 1; i <= input; ++i)
	{
		cin >> num[i];
		dp[i] = 0;
	}

	int result = -1000;
	for (int i = 1; i <= input; ++i)
	{
		dp[i] = max(num[i], num[i] + dp[i - 1]);
		if (result < dp[i])
			result = dp[i];
	}

	cout << result << endl;
	delete[] dp;
	delete[] num;
}