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

general
, , , , ,
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.