How to divide a circular array into k group of contiguous element such that difference between maximum sum and minimum sum is minimum. Each group have contiguous element of array. For e.g If the array is as follow. [6 13 10 2] and k=2 then o/p should be 18(6+10+2)-13=5. As array is circular 6,10,2 are contiguous element of array.
For e.g If the array is as follow. [100 92 133 201 34 34 34 94 108] and k=4 then group as follow 208(108,100), 225(92,133), (201), 196(34,34,34,94) so 225-196=29
I was thinking of binary search similar to painter's partition problem, please clarify if the approach is correct.
Can u provide a link to the question...
It was a company question from an online test, which I don't have access now.
You can try to maximize the minimum sum of group among different combinations, then the maximum sum of group will be relatively smaller. You can binary search over the minimum sum of group.
UPD: My approach is wrong. Someone please tell a correct approach. Specifically how to group elements in case when array is
20 20 30 100 50 200and we have divide it in 3 partitions.can u give proof for this solution??
Can someone give the correct approach for this question it seems a good question....