UVA - 10891 - Game of Sum

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        String m="";
        while(true){
            int n=Integer.parseInt(br.readLine());
            if(n==0){
                break;
            }
            StringTokenizer str=new StringTokenizer(br.readLine());
            int[]arr=new int[n];
            for(int i=0;i<n;i++){
                arr[i]=Integer.parseInt(str.nextToken());
            }
            long[][]dp=new long[n][n];
            for(int i=0;i<n;i++){
               for(int j=0;j<n;j++){
                   dp[i][j]=Long.MIN_VALUE;
                }
            }
            sb.append(maxSum(0, n-1, arr, dp)).append("\n");
        }
        System.out.print(sb);
    }
 
    static long maxSum(int i,int j,int[] arr,long[][]dp){
        if(i==j)
            return arr[i];
        if(dp[i][j]>Long.MIN_VALUE){
            return dp[i][j];
        }
        long sum=0;
        long value=Long.MIN_VALUE;
        for(int k=i;k<j;k++){
            sum+=arr[k];
            value=Math.max(value,sum-maxSum(k+1, j, arr, dp));
        }
        value=Math.max(value,sum+arr[j]);
        sum=0;
        for(int k=j;k>i;k--){
            sum+=arr[k];
            value=Math.max(value,sum-maxSum(i, k-1, arr, dp));
        }
        dp[i][j]=Math.max(value,sum+arr[i]);
        return dp[i][j];
    }
}