So, for example let's have the array {2, 80, 50, 42, 1, 1, 1, 2}. The best partitioning according to the problem is { {2, 80}, {50}, {42, 1, 1, 1, 2} }, so the output of the program in this case would be 82.

I have already thought of a \$O(n^2)\$ algorithm, but isn't there any better ( e.g. \$O(n)\$ or \$O(n\log n)\$  ) algorithm?

My \$O(n^2)\$ algorithm is (it is in C++):

So, for example let's have the array:

{2, 80, 50, 42, 1, 1, 1, 2}

The best partitioning according to the problem is:

{ {2, 80}, {50}, {42, 1, 1, 1, 2} }

so the output of the program in this case would be 82.

I have already thought of a \$O(n^2)\$ algorithm, but isn't there any better (e.g. \$O(n)\$ or \$O(n\log n)\$) algorithm?

My \$O(n^2)\$ algorithm: