package xj;
import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;
public class DaQiqiu { static int T, N, maxsum; static int data[]; static int num[]; static boolean used[];
public static void main(String[] args) throws FileNotFoundException { /* Scanner sc=new Scanner(System.in); */ Scanner sc = new Scanner(new File("src/DaQiqiu")); T = sc.nextInt(); for (int t = 0; t < T; t++) { N = sc.nextInt(); data = new int[N]; used = new boolean[N]; num=new int[N]; for (int i = 0; i < N; i++) { data[i] = sc.nextInt(); } maxsum = 0; dfs(0,0);
/* * for (int i = 0; i < N; i++) { System.out.print(" "+data[i]); } */
System.out.println(maxsum); } }
private static void dfs(int step, int sum) { if (step == N) { if (maxsum < sum) { maxsum = sum; } return; } for (int i = 0; i < N; i++) { if (!used[i]) { int l = -1; int r = -1; int t = sum; // you for (int j = i + 1; j < N; j++) {//这里一开始弄混淆了i和step if (!used[j]) { r = j; break; } } // zuo for (int j = i - 1; j >= 0; j--) { if (!used[j]) { l = j; break; } } // if (l == -1 && r != -1) { sum += data[r]; } // if (l != -1 && r == -1) { sum += data[l]; } // if (l != -1 && r != -1) { sum += data[l] * data[r]; } // if (l == -1 && r == -1) { sum += data[i]; } used[i] = true; dfs(step + 1, sum); used[i] = false; sum = t; } } } }
//input
7 5 3 10 1 2 5 7 12 48 28 21 67 75 85 6 2 3 4 6 7 1 4 1 2 3 4 10 1 2 1 4 5 6 7 8 9 10 5 1 2 3 4 5 3 2 8 3
//output
100 16057 84 20 360 40 24
