BOJ 13398 - 연속합 2

문제

BOJ 13398 - 연속합 2

N개의 정수로 이루어진 임의의 수열이 있다. 연속된 몇 개의 수를 선택하여 구할 수 있는 합 중 가장 큰 합을 구하려 한다. 단, 수는 한 개 이상 선택해야 하며, 최대 하나의 수를 제거할 수 있다.

기본 연속합 문제와 달리, 임의의 원소 하나를 제거하고 연속합의 최댓값을 구할 수 있다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에 N개의 정수가 주어진다. 각 정수는 -1,000보다 크거나 같고, 1,000보다 작거나 같다.

출력

가장 큰 연속 합(최대 하나 제거 가능)을 출력한다.

예제

입력

10
-1 5 -2 -9 8 -1 -3 5 0 -1

출력

풀이

핵심 아이디어: dp[i][0]은 i번째까지 원소를 하나도 제거하지 않았을 때의 최대 연속합, dp[i][1]은 i번째까지 원소를 정확히 하나 제거했을 때의 최대 연속합으로 정의한다.

점화식 설계:
- dp[i][0] = max(dp[i-1][0] + arr[i], arr[i]) — 제거 없이 i를 포함하는 최대 연속합
- dp[i][1] = max(dp[i-1][0], dp[i-1][1] + arr[i]) — 제거를 하나 사용한 경우
  - dp[i-1][0]: 이전까지 제거 없이 최대였던 구간에서 arr[i]를 제거
  - dp[i-1][1] + arr[i]: 이미 하나를 제거한 상태에서 arr[i]를 이어 붙임
초기값: dp[0][0] = arr[0], dp[0][1] = arr[0] (첫 원소를 "제거"하는 경우도 arr[0]으로 시작)
정답: 전체 순회하면서 max(dp[i][0], dp[i][1])의 최댓값을 갱신한다.

2차원 DP로 "제거 여부"를 상태로 표현하는 것이 핵심이다. 이 방법은 카데인 알고리즘의 확장이다.

코드

package day349;
 
import java.util.*;
import java.io.*;
 
public class Day343BOJ13398연속합2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        int[][] dp = new int[N][2];
 
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
 
        int max = arr[0];
        dp[0][0] = arr[0];
        dp[0][1] = arr[0];
 
        for (int i = 1; i < N; i++) {
            dp[i][0] = Math.max(dp[i - 1][0] + arr[i], arr[i]);
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1] + arr[i]);
            max = Math.max(max, Math.max(dp[i][0], dp[i][1]));
        }
 
        System.out.println(max);
        br.close();
    }
}

복잡도

시간: O(N) — 배열을 한 번 순회
공간: O(N) — dp[N][2] 배열

문제

BOJ 13398 - 연속합 2

기본 연속합 문제와 달리, 임의의 원소 하나를 제거하고 연속합의 최댓값을 구할 수 있다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에 N개의 정수가 주어진다. 각 정수는 -1,000보다 크거나 같고, 1,000보다 작거나 같다.

출력

가장 큰 연속 합(최대 하나 제거 가능)을 출력한다.

예제

입력

10
-1 5 -2 -9 8 -1 -3 5 0 -1

출력

풀이

점화식 설계:
- dp[i][0] = max(dp[i-1][0] + arr[i], arr[i]) — 제거 없이 i를 포함하는 최대 연속합
- dp[i][1] = max(dp[i-1][0], dp[i-1][1] + arr[i]) — 제거를 하나 사용한 경우
  - dp[i-1][0]: 이전까지 제거 없이 최대였던 구간에서 arr[i]를 제거
  - dp[i-1][1] + arr[i]: 이미 하나를 제거한 상태에서 arr[i]를 이어 붙임
초기값: dp[0][0] = arr[0], dp[0][1] = arr[0] (첫 원소를 "제거"하는 경우도 arr[0]으로 시작)
정답: 전체 순회하면서 max(dp[i][0], dp[i][1])의 최댓값을 갱신한다.

2차원 DP로 "제거 여부"를 상태로 표현하는 것이 핵심이다. 이 방법은 카데인 알고리즘의 확장이다.

코드

package day349;
 
import java.util.*;
import java.io.*;
 
public class Day343BOJ13398연속합2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        int[][] dp = new int[N][2];
 
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
 
        int max = arr[0];
        dp[0][0] = arr[0];
        dp[0][1] = arr[0];
 
        for (int i = 1; i < N; i++) {
            dp[i][0] = Math.max(dp[i - 1][0] + arr[i], arr[i]);
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1] + arr[i]);
            max = Math.max(max, Math.max(dp[i][0], dp[i][1]));
        }
 
        System.out.println(max);
        br.close();
    }
}

복잡도

시간: O(N) — 배열을 한 번 순회
공간: O(N) — dp[N][2] 배열