Write an algorithm, the given sequence seq from n Numbers with 3 <= n <= 1000 and every number k in the seq 1 <= k <= 200, maximum sum by repeatedly removing a number from seq, except the first and last number in seqand adding its value to the sum of two adjacent numbers. The algorithm ends when only two numbers are left.
Example: The maximum sum for the sequence [2, 1, 5, 3, 4] is 31.
So far, I've written a brute-force algorithm that checks all possible combinations but is not well suited to large sequences.
My question is, is there a more efficient algorithm that solves this problem?