[백준 BOJ][C++]1912번 연속 합 풀이: DP

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

1912번: 연속합

 

 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. 

 

dp[n]은 수열 arr의 n번째 원소까지의 연속합의 최댓값입니다. 

 

문제 예제인 10 -4 3 1 5 6 -35 12 21 -1 을 보겠습니다. 

 

arr[0]인 10까지의 최대 합은 당연히 10이겠지요? dp[0]=arr[0]=10으로 초기화 합니다. 

 

 

arr[1]인 -4까지의 최대 합을 보겠습니다. 

dp[0]+arr[0]	6
arr[0]	-4

이때의 최댓값은 10+(-4)로 arr[1]까지의 연속합의 최댓값은 6이므로 dp[1]=6입니다. 

 

 

arr[2]인 3까지의 최대 합을 보겠습니다. 

dp[1]+arr[2]	9
arr[2]	3

dp[2]=9가 됩니다. 

 

 

 그럼 dp[i]의 점화식을 한 번 볼까요?

 

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

 

 

이 과정을 dp[N-1]까지 반복하여 dp값 중 최댓값이 답이 됩니다. 

 

 

다음은 전체 코드입니다. 

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>

using namespace std;

#define MAX 100001

int dp[MAX];
int arr[MAX];

int main(void) {

	int N;
	int ans;
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	dp[0] = arr[0];
	ans = arr[0];
	for (int i = 1; i < N; i++) {
		dp[i] = max(arr[i], dp[i - 1] + arr[i]);
		ans = max(dp[i], ans);
	}

	cout << ans;

	return 0;
}