Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.4 kB
7
Indexable
Never
package GameWithNumbers;

import java.io.FileInputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("input.txt"));
        System.setOut(new PrintStream("output.txt"));
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 1; t <= tc; t++) {
        	int n = sc.nextInt();
        	int[] a = new int[n];
        	int[][]f = new int[n][n];
        	int sum = 0;
        	for(int i=0;i<n;i++){
        		a[i] = sc.nextInt();
        		sum+=a[i];
        	}
        	for(int i=0;i<n;i++){
        		f[i][i] = a[i];
        	}
        	for(int k=1;k<n;k++){
        		for(int i=0;i<n-k;i++){
        			f[i][i+k] = Math.max(a[i]-f[i+1][i+k], a[i+k]-f[i][i+k-1]);
        		}
        	}
        	
        	int score = (sum+f[0][n-1])/2;
        	
        	for(int i = 0;i<n-1;i++){
        		f[i][i+1] = Math.max(a[i], a[i+1]);
        	}
        	for(int k=2;k<n;k++){
        		for(int i=0;i<n-k;i++){
        			f[i][i+k] = Math.max(a[i]+Math.max(f[i+2][i+k],f[i+1][i+k-1]),
        					a[i+k]+Math.max(f[i][i+k-2], f[i+1][i+k-1]));
        		}
        	}
        	int score2 = f[0][n-1];
        	System.out.println("Case #"+t);
        	System.out.println(score2+" "+score);
        }

	}
	

}