[BOJ 13398] 연속합 2

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

13398번: 연속합 2

---

위 문제는 연속합을 구하는 문제를 조금 바꾸어서 풀 수 있다.

 

dp배열을 한 개를 제거했을 때, 제거하지 않았을 때로 나누어서 문제를 풀면 된다.

dp[i][0] = 한 개를 제거하지 않고 i번째까지의 가장 큰 연속합

dp[i][1] = 한 개를 제거하고 i번째까지의 가장 큰 연속합

이렇게 나누어서 풀면된다.

 

제거하지 않고 구하는 건 max(0, dp[i - 1][0]) + a[i] (a[i]는 i번째 값)를 통해서, 이전 값이 0보다 작다면 연속합이 줄기 때문에 0을 더한다.

 

1개를 제거하고 구하는 것은 아래와 같이 두 가지로 나누어서 큰 값을 구하면 된다.

(1) 이전에 값을 지우고 현재 값은 더한다.

(2) 현재 값을 지운다.

 

(1)의 경우 이미 이전에 값을 지웠기 때문에 dp[i - 1][1](1개를 지운 값 중 이전까지 큰 연속합)에 현재 값 a[i]를 더하면 되고, (2)의 경우 현재 값을 지우기 때문에 dp[i - 1][0]을 dp[i][1]에 넣으면 된다. 물론 둘 중 더 큰 값을 할당해야 한다.

---

#include <stdio.h>
#define max(a, b) ((a) > (b)? (a):(b))

int n;
int a[100001];
int dp[100001][2];
int ans;

int main()
{
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
		scanf("%d", a + i);

	dp[0][0] = a[0];
	dp[0][1] = a[0];

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

	printf("%d", ans);
}