Problem: Given N elements, in one operation you can merge adjacent elements (i.e. sum them up into one element), you have to do exactly K operations, what is the minimum possible obtainable value of the maximum of the resultant array.

Example
Elements: 1 2 3
K : 1
Output: 3 (by merging 1 and 2 we get 3, if we merged 2 and 3 we would get 5 which is > 3)

I can do this problem in O(N^2) complexity by Dynamic Programming, but can better time complexity be achieved?