# Untitled

unknown
plain_text
18 days ago
1.7 kB
0
Indexable
Never
```class Solution
{
static Scanner sc;
static int sum;
static int[] balls;
static int[] visited;
static int maxSum = 0;

public static void main(String args[]) throws Exception {

sc = new Scanner(System.in);
int T;
T = sc.nextInt();

for (int test_case = 1; test_case <= T; test_case++) {
sum = 0;
maxSum = 0;

int n = sc.nextInt();
balls = new int[n];
visited = new int[n];
for (int i = 0; i < n; i++) {
balls[i] = sc.nextInt();
}
banBong(0, 0);
System.out.println("Case #" + test_case);
System.out.println( maxSum);
balls = visited = null;
}
}

private static void banBong(int i, int s) {

if (i == balls.length - 2) {
int maxS = getMaxUnvisited();
s += maxS * 2;
maxSum = Math.max(maxSum, s);
return;
}

for (int j = 0; j < balls.length; j++) {
if (visited[j] == 0) {
int currentS = getScore(j);
visited[j] = 1;
banBong(i + 1, s + currentS);
visited[j] = 0;
}
}
}

static int getMaxUnvisited() {
int max = 0;
for (int i = 0; i < balls.length; i++) {
if (visited[i] == 0) {
max = Math.max(max, balls[i]);
}
}
return max;
}

static int getScore(int j) {
int result = 0;
int l = 0, r = 0;
for (int i = j + 1; i < balls.length; i++) {
if (visited[i] == 0) {
r = balls[i];
break;
}
}
for (int i = j - 1; i >= 0; i--) {
if (visited[i] == 0) {
l = balls[i];
break;
}
}
if (l != 0 && r != 0) {
result = r * l;
} else if (l == 0) {
result = r;
} else if (r == 0) {
result = l;
} else {
result = balls[j];
}
return result;

}

static boolean checkBound(int j) {
return j >= 0 && j < balls.length && visited[j] == 0;
}
}```