For example, let us consider dividing the following array into 5 subarrays:
The optimal way to divide this is [0,1,2],[1,3],,, 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?