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

 

 

<코드>

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

int n, ans;
int arr[100001];
int dp[100001][2];

int main() 
{
	ios::sync_with_stdio(0); 
	cin.tie(0); 

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

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

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


}

 

풀이 방법

dp[i][0] : 수열의 1~i번째 사이에서 가장 큰 연속 합

dp[i][1] : 수열의 1~i번째 사이에서 하나의 수를 제거했을 때 가장 큰 연속 합

 

 

www.acmicpc.net/problem/13398

13398번: 연속합 2