# Creating sum of all numbers within a sequence [duplicate]

Write an algorithm that, given sequence seq of n numbers where 3 <= n <= 1000 and each number k in seq 1 <= k <= 200, finds maximum sum by repeatedly removing one number from seq, except for first and last number in seq, and adding its value to sum of two adjacent numbers. Algorithm ends when there are only two numbers left.

For example: Max sum for sequence [2, 1, 5, 3, 4] is 31.

So far I've written brute force algorithm checking all possible combinations but it's not well suited for large sequences.

public static int solve(ArrayList<Integer> seq, int sumOfRemoved) {
if (seq.size() == 3) {
return seq.get(0) + seq.get(1) + seq.get(2) + sumOfRemoved;
}
for (int i = 1; i < seq.size() - 1; i++) {
ArrayList<Integer> clone = (ArrayList<Integer>) seq.clone();
clone.remove(i);
int sum = seq.get(i - 1) + seq.get(i) + seq.get(i + 1);
}
int max = 0;
for (int val : maxValues) {
max = Math.max(max, val + sumOfRemoved);
}
return max;
}


My question is, is there more efficient algorithm solving this problem?