# Untitled

unknown
plain_text
24 days ago
2.9 kB
9
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 - 3) {
int[] maintainBalls = new int[3];
int numOfMaintainBalls = 0;
for (int i = 0; i < N; i++) {
if (visited[i] == 0) {
maintainBalls[numOfMaintainBalls] = arr[i];
numOfMaintainBalls++;
}
}

int score1 = maintainBalls[1] + Math.max(maintainBalls[1], maintainBalls[2])*2;
int score2 = maintainBalls[0]*maintainBalls[2] + Math.max(maintainBalls[0], maintainBalls[2])*2;
int score3 = maintainBalls[1] + Math.max(maintainBalls[1], maintainBalls[0])*2;

score += Math.max(score1, Math.max(score2, score3));
if (res < score) {
res = score;
}
score -= Math.max(score1, Math.max(score2, score3));

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 if (N == 2) {
res = Math.max(arr[0], arr[1]) * 2;
}
else {
backtrack(0, 0);
}
System.out.println(res);
sc.close();
}
}```