To divide an array into k segments such that the minimum of the segments is the maximum



Given an array of n elements divide the elements into k segments such that the minimum sum of each of the segments is maximum


array is
10 5 8 7

and k is 2

the different ways to divide the array into two segment is

(10) , (5,8,7) min sum is 10

(10,5) (8,7) min sum is 15

(10,5,8) (7) min sum is 7

so the max of the minimum is 15 (7<10<15)

1< n , k < 10^5

how to attain the solution in O(n) or O(nlog n )


this can be done using binary search+greedy

Here link is a similar question and my solution link

comment if you have any doubt.


I hope this isnt related to an on going contest.


can you please explain your logic behind the code? Came across a similar problem, so would be of great help if you could.