I came up (I think, I just didn't see it anywhere) with this problem earlier today and I think it's better if I ask for help here as I still don't know its solution:
You have an array of N integers and in each step you can merge any 2 of them into a single integer (and then this integer is added to the array while the previous 2 are erased from it). The cost of merging two elements X and Y is max(X, Y).
You need to find the minimal cost you can get after merging all the integers into 1 (essentially, doing N — 1 merges).
Currently there's no constraint (not on N, nor on the limit of the integers) so just try to come up with the best complexity you can.
Examples:
input:
3
4 6 8
output:
16
(merging 4 and 6 to 10 with the cost of 6, and then merging 8 and 10 with the cost of 10, giving a total of 16).
input:
4
10 11 13 16
output:
55
(10->16) + (11->13) + (24->26) = 16 + 13 + 26 = 55.
Have you found a solution since then?
somewhat similar problem?
In this question you can only combine adjacent slimes, whereas in the question he posted, you can combine any two elements you want.
You can solve it in O(n^3) :)