# Untitled

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);
}

}

}
```