백준 13398번 - 연속합 2

문제

백준 13398번 - 연속합 2

아이디어

• 수를 제거하지 않은 경우와 수를 제거하는 경우 중에서 최대 부분합이 나올 수 있다.
• 수를 제거하지 않은 경우는 dp1[i] = max(dp1[i-1] + arr[i], arr[i]) 점화식으로 구할 수 있다. 연속된 부분을 이어가는 것과 새로운 부분을 시작하는 것 중 최댓값이다.
• 수를 제거하는 경우는 새로운 dp 배열과 수를 제거하지 않은 경우의 dp 배열을 활용해서 구할 수 있다. 점화식은 dp2[i] = max(dp2[i-1] + arr[i], dp1[i-1])이며 의미는 이전에 이미 수를 하나 제거했을 때 최대 부분합에 i번째 수를 더하는 것(dp2[i-1] + arr[i])과, i번째 수를 제거하는 것(dp1[i-1])중 최댓값이다.
• 차례대로 값을 구하면서 나온 최댓값이 정답이다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

코드 구현

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

public class BJ_13398 {
    public static void main(String[] args) throws IOException {

        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];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp1 = new int[n]; //수를 제거하지 않았을 때 i번째 최대 부분합
        int[] dp2 = new int[n]; //수를 제거했을 때 i번째 최대 부분합

        dp1[0] = arr[0];

        //수는 한 개 이상 선택해야 하므로 만약 n=1이면 하나의 수가 그대로 정답이다.
        int result = arr[0];

        for (int i = 1; i < n; i++) {
            dp1[i] = Math.max(dp1[i - 1] + arr[i], arr[i]);
            dp2[i] = Math.max(dp2[i - 1] + arr[i], dp1[i - 1]);
            result = Math.max(result, Math.max(dp1[i], dp2[i]));
        }

        System.out.println(result);
    }
}