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

algorithm
binary-search
search
segment-tree
subarray
sum

#1

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

eg

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 )


#2

this can be done using binary search+greedy

Here link is a similar question and my solution link

comment if you have any doubt.


#3

I hope this isnt related to an on going contest.


#4

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