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

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

13398번: 연속합 2

 

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

 

 dp[0][i] = i 번째 숫자까지의 연속 합의 최댓값

 dp[1][i] = 숫자 하나를 제거한 i 번째 숫자까지의 연속 합의 최댓값

 

 

연속 합의 풀이는 다음 링크를 참고해주세요:)

https://iridescent-zeal.tistory.com/47?category=1261302

 

문제 예제로 풀이 과정을 보겠습니다.

 

파란 색은 dp[0][i]를 나타내고 빨간색은 dp[1][i] 을 나타냅니다.

10	-4	3	1	5	6	-35	12	21	-1
10	6	9	10	15	21	-14	12	33	32
10	10	13	14	19	24	21	33	54	53

 

 여기서 주목할 지점은 음수입니다!

 

 두 번째 원소인 -4를 보겠습니다. dp[1][2]의 후보 값들은 어떤 것들이 있을 까요?

 

 -4를 포함하거나 포함하지 않거나 두 가지이겠죠!

 

 10과 10-4 중 최댓값인 10이 dp[1][2]가 됩니다.

 

 

 

 일곱 번째 원소인 -35를 보겠습니다. dp[1][7]의 후보는 어떤 것들이 있을 까요?

 

 역시 -35를 포함하거나 포함하지 않거나 두 가지 입니다.

 

포함한다면 -4를 제외한 것이겠죠? 그렇다면 dp[1][6] + -35가 될 것입니다.

 

포함하지 않는다면 dp[0][6] 값을 그대로 가져오면 되겠죠?

 

 

따라서 점화식은 다음과 같습니다. 

 

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

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

 

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<cstdlib>

using namespace std;

int dp[2][100001];
int arr[100001];

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	int ans;

	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	dp[0][1] = dp[1][1] = arr[1];
    ans = arr[1];

	for (int i = 2; i <= n; i++) {
		dp[0][i] = max(arr[i], dp[0][i - 1] + arr[i]);
		dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + arr[i]);

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

	cout << ans;

	return 0;
}