소프티어

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


public class Main {


    static final int MIN = -1000;
    static int n;
    static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());


        n = Integer.parseInt(stk.nextToken());
    
        arr = new int[n];
        
        stk = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(stk.nextToken());
        }


        int[] sum = new int[n];
        sum[0] = arr[0];
        for(int i = 1; i < n; i++){
            sum[i] = sum[i - 1] + arr[i];
        }

        // 0 => 구간 하나 구한경우
        // 1 => 구간 두개 구한경우
        int[][] dp = new int[n][2];
        for(int i = 0; i < n; i++){
            dp[i][0] = arr[i];
            dp[i][1] = MIN;
        }


        for(int i = 1; i < n; i++){
            // 구간을 하나만 구한 경우 => 이전까지의 최대 또는 현재까지의 누적합 또는 arr[i]
            int prevOrSum = Math.max(dp[i-1][0], sum[i]);
            dp[i][0] = Math.max(dp[i][0], prevOrSum);
            for(int j = 0; j < i; j++){
                dp[i][0] = Math.max(dp[i][0], sum[i] - sum[j]);
            }
            
            // 구간을 두개 둔 경우 => 어느 위치를 기준으로 구간을 나눴는지가 중요함
            // 나눌 수 있는 위치는 1번부터 현재위치 - 1 
            for(int j = 1; j < i; j++){
                // 현재 dp값과 왼쪽 최대 vs 오른쪽 포함한 새로운 구간합 비교
                int leftOrRight = Math.max(dp[i - 1][1], dp[j-1][0] + (sum[i] - sum[j]));
                dp[i][1] = Math.max(dp[i][1], leftOrRight);
            }
        }


        System.out.println(dp[n - 1][1]);
    }


   
}

나름 DP를 이용해서 구현했는데 시간초과가 나더군요..

혹시 다른 아이디어 힌트 가능할까요 ㅠ