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?
Well…Here is very basic and non optimal idea, without guarantee. I didn’t try to implement it.
You could try some DP. For each i and j, you store a list of couples (min,max) you can achieve by partitioning the array [A1…Ai] in j sub-arrays. Actually you don’t store the full list of (min,max). For given i/j/min you keep the lowest max. And for given i/j/max you keep the highest min. Also, for some given i and j, if you have min1,max1 and min2,max2 with min2<=min1 and max2>=max1, then you discard min2,max2.