Untitled

package Game_with_numbers;

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

public class Solution {
	static int res1, res2, n, sum;
	static int[] a;
	static int[][] f;
	
	public static int game1(){
		
		f = new int[n][n];
		for(int i = 0; i < n; i++){
			if(i<n-1){
				f[i][i+1] = Math.max(a[i], a[i+1]);
			}
			
			for(int j = 0; j < n; j++){
				if(i==j){
					f[i][j] = a[i];
				}
			}
		}
		
		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+1][i+k-1], f[i][i+k-2]) );
			}
		}
		res1 = f[0][n-1];
		return res1;
	}
	
	
	public static int game2(){
		
		f = new int[n][n];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(i==j){
					f[i][j] = a[i];
				}
			}
		}
		
		sum = 0;
		for(int i = 0; i < n; i++){
			sum += 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]);
			}
		}
		res2 = (sum + f[0][n-1])/2;
		return res2;
	}	

	
	public static void main(String[] args){
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 0; t < test; t++) {
			n = scanner.nextInt();
			a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = scanner.nextInt();
			}
			res1 = 0;
			res2 = 0;
			
			game1();
			game2();
			
			
//			System.out.println(n);
			System.out.println("Case #" + (t + 1) + "\n" + res1 + " " + res2);
		}
		scanner.close();
	}
}