For example, let us consider dividing the following array into 5 subarrays:

[0,1,2,1,3,1,5,6]

The optimal way to divide this is [0,1,2],[1,3],[1],[5],[6] since the maximum sum subarray has sum 6 and minimum sum subarray has sum 1, and 5 is the best possible result that you can get.

The algorithm that I can think of iterates through all possible ways of partitioning the array into k parts and choosing the best of them all. This is clearly exponential. Is there a polynomial time algorithm?