[백준] 연속합2 13398번 C++ 풀이

 

 

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

13398번: 연속합 2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[100001][2];
vector<int> v;
int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		v.push_back(num);
	}

	int res = v[0];

	for (int i = 0; i < N; i++)
	{
		dp[i][0] =dp[i][1] =v[i];
		if (i != 0) {
			dp[i][0] = max(dp[i][0],dp[i -1][0]+ v[i]);
			dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]+v[i]);
		}
		res = max(res, max(dp[i][0], dp[i][1]));
	}
	cout << res;

}

dp[i][0] : i번째까지의 최대 연속합인데 삭제를 사용하지 않은 경우

dp[i][1] : i번째까지의 최대 연속합인데 삭제를 이미 사용했거나 이번에 사용할 경우

 

dp[i][0] =dp[i][1] =v[i];

일단 dp[i][0]과 dp[i][1]은 i번째의 값으로 초기화를 시켜줍니다.

왜냐하면 i번째 앞전에 구한 최대합 보다 i번째 자체만으로도 최댓값이 될 수 있기 때문입니다.

그 다음 dp[i][0]과 dp[i][1]을 max를 이용해 최대 값으로 초기화 시켜주면 됩니다.

 

dp[i][0] = max(dp[i][0],dp[i -1][0]+ v[i]);

dp[i][0]에 들어올 수 있는 값은 현재 dp[i][0] 과 dp[i-1][0] ( dp i-1번째,삭제 미사용 경우 )에 i번째 수를 더한 값 중

더 큰 값 입니다.

 

dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]+v[i]);

dp[i][1]에 들어올 수 있는 값은 dp[i-1][0]로 앞전에 삭제를 사용하지 않았고 이번 i번째수를 삭제를 예정한 경우와

이미 삭제를 사용한 앞전의 최댓값인 dp[i-1][1]에 현재 i번째 수를 더한 값 중 더 큰 값입니다.

 

res = max(res, max(dp[i][0], dp[i][1]));

어느 구간에서 최댓값이 발생할지 모르니 모든 구간의 삭제를 사용한 경우와 안 사용한 경우를 비교하여 결괏값 res를 그때그때 초기화시켜 줍니다.