[BOJ-13398]연속합 2

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

연속합 문제에서 그 연속합 중 

수열 중 

- 하나를 제거 혹은 

- 하나를 제거하지 않는 경우( 수열을 온전히 다 더한 경우) 

로 경우를 추가한다. 

단, 1개의 수는 무조건 선택한다. 

1

-1

이런 경우에 답은 -1임을 의미함.

[입력]

n

a1 ... an

위와 같은 입력이 주어지며

4

2 -30 3

인 경우 -30을 연속합의 수열 중 제거 가능한 수이므로 답은 5가 된다.

[출력]

하나를 제거/ 제거하지 않았을 때 연속합의 최대값을 출력한다.

[접근방법]

처음 이 문제를 접근할 때 

임의의 연속합 구간 [a, b]

0) O..........O : 모두 선택했을 때 [a,b] 최대값

1) O........OX : 마지막 b번째를 제외한 상태에서 최대값 [a,b-1] : 이것은 0) 의 경우 b-1에 속함.

2) O..OXO..O : 제외한 값이 끼어있고 현재값은 무조건 선택한 연속합.

으로 경우를 나누어 보았다. 

 

그럼 이 경우에서 값이 연속적으로 나올 수 있었다. 

 

memo[0][i] = memo[0][i-1] + input[i];

memo[1][i] = memo[0][i-1];

memo[2][i] = max(memo[0][i-1], memo[2][i-1]) + input[i];

1)의 경우가 메모리 낭비라는 걸 알고 제외시켰다.

 

 

memo[0][i] = memo[0][i-1] + input[i];

memo[1][i] = max(memo[0][i-2], memo[1][i-1]) + input[i];

 

그런데 만약에 갱신되지 않았을 경우에는 어떻게? 해야하는지 이런 경우에는 저장된 값이 0이므로 음수의 값을 ans이 갖고 있는 경우 0으로 갱신이 되어버리는 경우가 발생해 boolean 배열을 만들어 갱신 되었을 경우만 ans과 최대값 비교를 하게 만들었다. ( is_update )

#include<cstdio>
 
const int MAX = 111111;
const int INF = 1111;
int input[MAX];
int memo[2][MAX];
bool is_update[2][MAX];
int ans = -INF;
int n;
int max2(int a, int b) {
    return (a > b) ? a : b;
}
 
void init() {
    for (int i = 0; i < n; i++) memo[1][i] = -INF;
}
 
int main() {
    scanf("%d", &n);
    init();
    for (int i = 1; i <= n; i++) {
        scanf("%d", &input[i]);
        ans = max2(ans, input[i]);
 
        if (n == 1) break;
 
        if (memo[0][i - 1] + input[i] > 0) memo[0][i] = memo[0][i - 1] + input[i], is_update[0][i] = true;
 
        if (i - 2 >= 0) {
            int condition = -INF;
            if (is_update[0][i - 2]) condition = max2(condition, memo[0][i - 2]);
            if (is_update[1][i - 1]) condition = max2(condition, memo[1][i - 1]);
            if (condition != -INF) memo[1][i] = condition + input[i], is_update[1][i] = true;
        }
        if (is_update[0][i]) ans = max2(ans, memo[0][i]);
        if (is_update[1][i]) ans = max2(ans, memo[1][i]);
        //printf("%5d / %5d %5d\n", input[i], memo[0][i], memo[1][i]);
    }
 
    printf("%d\n", ans);
    return 0;
}
// 3
// -1 -1 -1
// ans : -1
 
// 1
// -1
// ans : -1