# Untitled

unknown
plain_text
a year ago
1.8 kB
1
Indexable
Never
```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();
}
}
```