# Untitled

unknown
plain_text
2 months ago
1.7 kB
1
Indexable
Never
```import java.util.Scanner;

public class Solution {
static int n;
static int[] a;
static int[] visit;
static int[] res;
static int max;

public static void main(String args[]) throws Exception{
//System.setIn(new FileInputStream("src/BanBongBay/input.txt"));
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++){
n = sc.nextInt();
a = new int[n];
visit = new int[n];
res = new int[n];
for(int i = 0; i < n; i++){
a[i] = sc.nextInt();
}

max = 0;

if(check()){
max = a[0]*a[0]*(n-2) + a[0]*2;
}else{
Try(0, 0);
}
System.out.println("Case #" + test_case);
System.out.println(max);
}
}

public static boolean check(){
for(int i = 0; i < n; i++){
if(a[i] != a[0]){
return false;
}
}
return true;
}

public static void Try(int k, int diem){
if(k == n){
if(diem > max){
max = diem;
}
return;
}
for(int i = 0; i < n; i++){
if(visit[i] == 0){
visit[i] = 1;
int td1 = -1;
for(int z = i-1; z >= 0; z--){
if(visit[z] == 0){
td1 = z;
break;
}
}
int td2 = -1;
for(int z = i+1; z < n; z++){
if(visit[z] == 0){
td2 = z;
break;
}
}

if(td1 != -1 && td2 != -1){
Try(k+1, diem + a[td1]*a[td2]);
}else if(td1 == -1 && td2 != -1){
Try(k+1, diem + a[td2]);
}else if(td1 != -1 && td2 == -1){
Try(k+1, diem + a[td1]);
}else if(td1 == -1 && td2 == -1){
Try(k+1, diem + a[i]);
}
visit[i] = 0;
}
}
}
}
```