[Gold 5] 13398번 연속합 2

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] arr = br.readLine().split(" ");
        int[] dp1 = new int[n];
        int[] dp2 = new int[n];
        int ans = Integer.parseInt(arr[0]);
        dp1[0] = dp2[0] = Integer.parseInt(arr[0]);
        
        for(int i=1; i<n; i++) {
            dp1[i] = Math.max(dp1[i-1]+Integer.parseInt(arr[i]), Integer.parseInt(arr[i]));
            dp2[i] = Math.max(dp2[i-1]+Integer.parseInt(arr[i]), dp1[i-1]);
            ans = Math.max(ans, Math.max(dp1[i], dp2[i]));
        }
        
        System.out.println(ans);
    }
}