# Untitled

unknown
plain_text
22 days ago
2.5 kB
4
Indexable
Never
```import java.io.*;
import java.util.*;

public class Solution {
public static int N, res;
public static int[] arr, visited;

public static int countScore(int x) {
int leftScore = 0;
int rightScore = 0;
for (int i = x - 1; i >= 0; i--) {
if (visited[i] == 0) {
leftScore = arr[i];
break;
}
}

for (int i = x + 1; i < N; i++) {
if (visited[i] == 0) {
rightScore = arr[i];
break;
}
}

if (leftScore != 0 && rightScore != 0) {
return leftScore*rightScore;
}
else if (leftScore == 0 && rightScore != 0) {
return rightScore;
}
else if (leftScore != 0 && rightScore != 0) {
return leftScore;
}
else {
return arr[x];
}
}

public static void backtrack(int step, int score) {

if(step == N - 2) {
int[] maintainBalls = new int[2];
int numOfMaintainBalls = 0;
for (int i = 0; i < N; i++) {
if (visited[i] == 0) {
maintainBalls[numOfMaintainBalls] = arr[i];
numOfMaintainBalls++;
}
}

score += Math.max(maintainBalls[0], maintainBalls[1])*2;
if (res < score) {
res = score;
}
score -= Math.max(maintainBalls[0], maintainBalls[1])*2;
return;
}

for (int i = 0; i < N; i++) {
if (visited[i] == 0) {
visited[i] = 1;
backtrack(step+1, score+countScore(i));
visited[i] = 0;
}
}
}

public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
arr = new int[N];
visited = new int[N];
res = 0;
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt();
}

if (N == 1) {
res = arr[0];
}
else {
backtrack(0, 0);
}
System.out.println(res);
sc.close();
}
}```