1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;
class Main{
    static int[][] dp;
    static int[] sum;
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        sum = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scan.nextInt();
            if(i>0){
               sum[i] += sum[i-1]+arr[i];
            }
            else{
                sum[i] = arr[i];
            }
        }
        int sum = 0;
        dp = new int[n][n];
        for(int i=0;i<n;i++){
            Arrays.fill(dp[i],Integer.MIN_VALUE);
        }
        sum = compute(arr,0,n-1);
        System.out.println(sum);
    }
    public static int compute(int[] arr,int start,int end){
        if(start==end){
            dp[start][start] = arr[start];
            return dp[start][start];
        }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX