Need help with a binary search question

Revision en1, by Sudhanshu_Kumar, 2019-10-08 21:45:10

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.

Tags #binary search, #help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Sudhanshu_Kumar 2019-10-08 21:45:10 656 Initial revision (published)