연속합 2

이 문제는 연속합 문제에서 조건이 추가된 문제로, 추가된 조건은 "수열에서 수를 하나 제거할 수 있다.(제거하지 않아도 된다)" 입니다.

그러면 우선 기존 연속합 문제에서 생각을 출발해보면 되는데, 기존 연속합 문제는 다음과 같은 성질을 이용해서 풀었습니다.

• 연속합이므로, 음수가 아닌 수들은 무조건 연속해서 더하는 것이 이득이다.
• 음수를 더한다고 해도, 그 이후의 숫자들을 더했을 때 더 커질 수 있으므로 일단 합쳐봐야 한다.
• 현재 수를 더했는데, 현재 더한 수보다 합이 작은 경우, 현재의 수를 시작으로 하는 수열을 선택하는 것이 이득이다.

연속합 2는 이런 아이디어에서, 숫자 하나를 배제할 수 있는 상태가 추가된 것입니다. 따라서, 기존의 점화식인 아래와 같은 점화식에

// f(n)은 수열 S에서 n번부터 시작하는 수열의 최대 연속합
f(n) = max(S[n], f(n-1) + S[n])

추가적으로 숫자를 제외했을때와 제외하지 않았을 때의 상태를 고려하면 됩니다.

// f(n, 0)은 수열 S에서 n번부터 시작하는 수열의 최대 연속합 중, 숫자가 제외되지 않았을 때의 값
// f(n, 1)은 수열 S에서 n번부터 시작하는 수열의 최대 연속합 중, 숫자가 제외됐을 때의 값

// 기존 연속합 (숫자를 제외하지 않은 경우)
f(n, 0) = max(S[n], f(n-1) + S[n])

// 숫자를 하나 제외한 경우

// 1. 현재 숫자 S[n]을 제외한 경우
// 현재 숫자를 제외한 것이므로, 이전 제외되지 않은 경우인 f(n-1, 0)을 사용하면 된다.
g(n) = f(n-1, 0)

// 2. 이미 제외된 숫자가 있는 경우
// 이미 숫자가 제외되었으므로, 이전 f(n-1, 1)에다가 현재 수를 더하면 된다.
h(n) = f(n-1, 1) + S[n]

// 이제 g와 h중 최댓값을 선택하면 된다.
f(n, 1) = max(g(n), h(n))

다음과 같은 식을 구현한 코드는 아래와 같습니다.

package bj.comito.codeplus.basic.week06;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ13398 {
    private static int N;
    private static int[] sequence;

    public static void main(String[] args) throws Throwable {
        init();

        System.out.println(dp());
    }

    private static void init() throws Throwable {
        final BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in), 1<<10
        );

        N = Integer.parseInt(br.readLine());

        final StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        sequence = new int[N];
        for (int ni = 0; ni < N; ni++) {
            sequence[ni] = Integer.parseInt(st.nextToken());
        }

        br.close();
    }

    private static int dp() {
        if (N == 1) {
            return sequence[0];
        }

        int ans = sequence[0];

        // cache[n]은 n까지의 수열 중 최대 연속합
        // cache[n][0]은 수를 빼지 않은 경우의 최대 연속합
        // cache[n][1]은 수를 하나 뺀 경우의 최대 연속합
        final int[][] cache = new int[N][2];
        cache[0][0] = sequence[0];

        for (int ni = 1; ni < N; ni++) {
            // 수를 빼지 않는 경우는
            // 기존 연속합처럼 구한다.
            cache[ni][0] = Math.max(cache[ni-1][0] + sequence[ni], sequence[ni]);

            // 수를 빼는 경우는
            // 1. 얘를 처음 빼는 경우
            // 2. 이전에 뺀 경우
            cache[ni][1] = Math.max(cache[ni-1][0], cache[ni-1][1] + sequence[ni]);

            ans = Math.max(
                    ans,
                    Math.max(cache[ni][0], cache[ni][1])
            );
        }

        return ans;
    }
}