Given an array of integers, divide the array into k subarrays such that the difference between the maximum sum and minimum sum subarrays is minimised

Asked Nov 08 '15 at 08:53

Active Nov 08 '15 at 09:19

Viewed 1,399 times

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?

asked Nov 08 '15 at 08:53

Somebody

Binary search...is the Sol. Same ques has been asked a few days back and I've answers it myself... – vish4071 Nov 08 '15 at 09:03
can you please provide link to that question/solution? – Somebody Nov 08 '15 at 09:06
Sorry man...I'm using so app and don't know how to post links. You can check in my top posts, 3rd or 4th ans is to same ques. – vish4071 Nov 08 '15 at 09:20
yeah got it. However, are you sure the two problems are same/similar? – Somebody Nov 08 '15 at 09:29
@vish4071 - looked up your answers: http://stackoverflow.com/questions/32437090/how-to-partition-an-array-of-integers-in-a-way-that-minimizes-the-maximum-of-the/32437904#32437904 – shapiro yaacov Nov 08 '15 at 09:32
Yes...what do you think is the difference?? – vish4071 Nov 08 '15 at 09:40
the fact that we need to minimise the difference of maximum sum and minimum sum; which is different from minimizing the maximum sum subarray. – Somebody Nov 08 '15 at 09:42
I'm sorry, got caught up in words. – vish4071 Nov 08 '15 at 10:03

Given an array of integers, divide the array into k subarrays such that the difference between the maximum sum and minimum sum subarrays is minimised

0 Answers0