I had encountered this question somewhere !
An array A of size N is given and we have to divide the array into K sub-arrays such that the value of the array is minimal.And the value of array is summation of value of all sub arrays ,so the value of each sub array is the greatest element present in the sub-array, we have to print the minimum possible value of the array, if the value cannot be obtained print -1.
CONSTRAINTS:
1<=N<=1000
1<=A[i]<=1000
1<=K<=30
EXAMPLES:
A=[3,5,7,2,1,8,3,3,3]
N=9
K=4
Answer:17
Explanation:
{3,5,7,2,1,8},{3},{3},{3} = 8+3+3+3=17
A=[3,1,1,1,8]
N=5
K=3
Answer:12
Explanation:
{3} , {1,1,1},{8} = 3 + 1 + 8 =12
Example 3:
A={1,1,1,1}
N=4
K=5
Answer: -1
Explanation: It cannot be split into 5 subarrays so return -1.
Any help will be really thankful