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

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

 

지난번 연속합과 달리 연속되는 수열 중 하나를 빼도 되는 조건이 붙었다.

 

연속합의 최대값을 구하는 방법은 dp를 이용하면 되는데

 

dp[100001], a[100001]을 int형으로 선언해주고, dp[i]는 i번째 수열로 끝나는 연속합의 최대값이다. 

 

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

 

코드로는 이렇다. 하지만 여기서 하나를 뺄 수 있다면 더 커질 수 있는 수열이 어떤것인지 찾아야한다.

 

하나를 빼는 경우와 안빼는 경우의 dp배열을 두가지 선언해 주고 그 중 더 큰값을 저장해주는 방법을 사용했다.

 

#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
int dp[MAX][2] = { 0, };
int a[MAX] = { 0, };
int main(int argc, char* argv[])
{
	int n;
	cin >> n;
 
	for (int i = 0;i < n;i++) {
		cin >> a[i];
	}
 
	int ans = a[0];
	dp[0][0] = a[0];
	dp[0][1] = a[0];
 
	for (int i = 1;i < n;i++) {
		dp[i][0] = max(dp[i - 1][0] + a[i], a[i]);
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][1] + a[i]);
		ans = max(ans, max(dp[i][0], dp[i][1]));
	}
 
	cout << ans << '\n';
 
	return 0;
}

 

다시 풀어봐야하는 문제