kingsubin

import java.io.*;
import java.util.StringTokenizer;

public class boj_13398 {
    static int[] dl; // i 번째를 마지막으로 하는 연속합
    static int[] dr; // i 번째를 시작으로 하는 연속합
    static int[] a;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        dl = new int[n+1]; dr = new int[n+1];
        a = new int[n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        // dl 
        for (int i = 1; i <= n; i++) {
            dl[i] = a[i];
            if (i > 1 && dl[i] < dl[i-1] + a[i]) {
                dl[i] = dl[i-1] + a[i];
            }
        }

        // dr 
        for (int i = n; i >= 1; i--) {
            dr[i] = a[i];
            if (i < n && dr[i] < dr[i+1] + a[i]) {
                dr[i] = dr[i+1] + a[i];
            }
        }

        // 제거하지 않는경우
        int ans = dl[1];
        for (int i = 1; i <= n; i++) {
            if (ans < dl[i]) {
                ans = dl[i];
            }
        }

        // i번째 수를 제거한 경우
        for (int i = 2; i <= n-1; i++) {
            if (ans < dl[i-1] + dr[i+1]) {
                ans = dl[i-1] + dr[i+1];
            }
        }

        System.out.println(ans);
    }
}

 

- 1~n까지 하나씩 제거했을경우의 dp를 만들까 생각했지만

- 1 <= n <= 100,000 이므로 O(n^2)으로는 풀이가 안됨, 그 이하의 시간복잡도 풀이 생각

 

- dl[i] : i번째를 끝으로 하는 연속합

- dr[i] : i번째를 시작으로 하는 연속합

- d[i] : i번째를 제거했을때의 연속합

- 3가지로 구분해주고, d에서 최댓값이 ans

- d[i] = dl[i-1] + dr[i+1]로 볼 수 있다. i 번째를 제거하면 dl[i-1], dr[i+1]이 연속하게 됨