[Solved]: Broken stick problem

Problem Detail: 

We have a broken stick. For every part, we know it's length. Our task is to connect all parts (glue them), that we will use as small amount of glue as possible.

The amount of glue need to connect two parts equal the maximum from their sizes. We can only glue two parts at one time.Can we solve this problem in the time complexity smaller than $O(n^3)$? I know only the answer, using dynamic table in this complexity

Asked By : Jonny

Answered By : Bojan Serafimov

You didn't define what 'connecting all parts' is. Do you need to arrange them in an array? Or just connect them?

The way I understood the problem, you can use Prim's algorithm to find the minimum spanning tree, and that's the result. O(n^2)

In case you want them arranged in an array, I think the sorted array is always optimal.

We will call a part "counted" if it is the bigger part in some connection. A part can be counted 0, 1, or 2 times. Let there be 3 elements in the array that are not sorted (A > B > C). Let L be the part placed left from this sequence, and R the part placer right. The ordering is L(permutation(A,B,C))R. You can observe all cases, and see that the permutation ABC is the best because it takes the parts max(L,A), A, B, max(C,R). This proves that all 3 element subsequences should be sorted, which means the sorted array is optimal.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7881