BOJ 13998 연속합 2

-1000 이상 1000 이하의 수 n개로 이루어진 임의의 수열이 주어지고 이 중 연속된 숫자 몇 개(한 개 이상)를 선택해서 그 합을 최대로 하려고 하는데, 수열에서 수 하나를 제거할 수 있다. 이 때, 최대인 합을 구하는 문제이다.

연속합 문제와 비슷하다. 수열에서 수 하나를 제거할 수 있다는 것이 추가됐다.
연속합 문제에서는 d[n] = n번째 수를 마지막 수로 하는 연속된 숫자들의 합의 최대값
으로 놓고 n번째 수와 d[n-1]의 합이 n번째 수보다 크면 d[n]을 d[n-1]+(n번째 수)로 갱신해주는 식으로 풀었다. 만약 아니라면 d[n]은 n번째 수의 값을 유지하는 식으로...
음수도 포함돼 있어서 d[n-1]과 n번째 수의 합이 n번째 수보다 작아진다면 합하지 않고, n번째 수부터 연속된 수열을 만들어 나가는 것이 이익이다.

자, 그런데 이 문제는 수열에서 하나의 수를 제거할 수 있어서 좀 까다롭다.
n제한이 10만이라 음수를 하나씩 제거 해보고 위의 방법으로 연속된 수열의 합의 최대값을 구하는 방법은 TLE를 받을 것이다.
그렇다면 어떻게 해야할까? 제거는 하나만 할 수 있다.
바로 d[n]에서 d[n][r] = n번째 수를 볼 때, 연속된 숫자들에서 하나의 수를 r번 제거 한 경우의 합의 최대값. (r=0 or 1)
으로 놓고, d[n][0]값은 n번째 수의 값을 가지고 있다고 할 때,
d[n][0] = MAX(d[n][0], d[n-1][0]+arr[n]) //제거하지 않는 경우.
d[n][1] = MAX(d[n-1][0], d[n-1][1]+arr[n]) // 직전까지 제거하지 않은 경우 n번째 수를 제거하고, 직전까지 한 번 제거 했다면 n번째 수는 제거하지 않고 더한다.

그리고 이 것은 그냥 제거를 안 한 수열의 합과, 제거를 한 번 한 수열의 합을 나타내는 변수 2개로 나타낼 수도 있다.
int rmSum; //제거를 한 번만 한 수열의 합
int Sum;  //제거를 한 번도 안 한 수열의 합

rmSum = MAX(Sum, rmSum+arr[n])
Sum = MAX(arr[n], Sum+arr[n])

그러면서 각 n에 대하여 rmSum과 Sum 중 최대값을 계속 갱신해주면 된다.
결국 위의 방법과 똑같다고 볼 수 있다.

주의해야 할 점으로 두 가지가 있다.
1. 음수로 구성되어 있을 경우 최대값이 음수가 나올 수 있다는 것.
2. 수열의 수가 한 개밖에 없을 경우, 그 값이 음수라도 선택해야 한다는 것.(문제에서 한 개이상의 수를 선택해야 한다는 조건이 있으므로)