[백준][13398번] 연속합2

문제 URL

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

전체 풀이

연속합1 문제의 변형문제다. 연속된 몇개의 수를 선택해서 최대의 합을 구하는 문제이다. 하지만 여기서 ‘i번째 수를 제외할 수 있다’는 조건이 더 추가되었다.

---

모든 원소를 제거해보며 최대합 알고리즘을 돌리는 것은 비효율적이다. 외냐하면 n은 1<=n<=100000의 범위를 가지기 때문이다.

---

따라서 연속합1에 했던 알고리즘을 활용하여
D[i] = i번째 수에서 끝나는 최대 연속합 DR[i] = i번째 수에서 시작하는 최대 연속합 을 계산하면된다. 즉, D[i-1] + DR[i+1]가 i번째를 제거했을때의 최대합을 구할 수 있다.

나의 풀이

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        int[] d = new int[n];
        int[] dr = new int[n];

        // d[i] = i 번째 수에서 끝나는 최대 연속합
        for (int i=0; i<n; i++) {
            d[i] = a[i];
            if (i > 0 && d[i] < d[i-1] + a[i]) {
                d[i] = d[i-1] + a[i];
            }
        }

        // dr[i] = i 번째 수에서 시작하는 최대 연속합
        for (int i=n-1; i>=0; i--) {
            dr[i] = a[i];
            if (i < n-1 && dr[i] < dr[i+1] + a[i]) {
                dr[i] = dr[i+1] + a[i];
            }

        }

        // i번째 수를 제외하지 않고 최대합 구하기
        int ans = d[0];
        for (int i=1; i<n; i++) {
            if (ans < d[i]) {
                ans = d[i];
            }
        }

        //i번째 수를 제외한 최대합 구하기
        for (int i=1; i<n-1; i++) {
            if (ans < d[i-1] + dr[i+1]) {
                ans = d[i-1] + dr[i+1];
            }
        }
        System.out.println(ans);
    }
}