[C/C++] 백준 1912번 - 연속합 (DP)

 

<코드>

#include<iostream>
#include<algorithm>
using namespace std;

int x, N;
int dp[100001];

int main()
{
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> x;
		if (i == 0)
		{
			dp[0] = x;
		}
		else
		{
			if (dp[i - 1] < 0) dp[i] = x;
			else dp[i] = dp[i - 1] + x;		
		}
	}

	sort(dp, dp + N, greater<>());
	cout << dp[0];
}

INDEX	0	1	2	3	4	5	6	7	8	9
Arr	10	-4	3	1	5	6	-35	12	21	-1
DP	10	6	9	10	15	21	-14	12	33	32

DP[x]의 값은 DP[x-1]값과 Arr[x]의 값을 합한 값인데 만약 DP[x-1]이 0보다 작을 경우 DP[x]의 값은 Arr[x]의 값이된다. 이렇게 하여 구한 DP의 최대값이 정답이 된다.

 

www.acmicpc.net/problem/1912

1912번: 연속합