An array of size n is given to you and you need to divide it into k parts such that the maximum of the resultant subarrays is minimized. And also print the configuration.
-1e6 <= A[i] <= 1e6
1 <= n,k <= 1e5
Your question and heading does not match. If you want to minimize the maximum sum over all subarrays, then it is a simple binary search problem.
Yes, I want to minimize the maximum sum over all the subarrays. And if the nos. are all positive or all negative we can do it easily. But in this neg pos any integer can be there. Try to think of a case where you are trying to calculate the sum of the subarray and it becomes greater than the mid value and then in that subarray just some negative value comes because of that the overall subarray is now reduced to a value lesser than the mid value.
I hope you understand what I am trying to say!!
@samarth2017 pls consider this example,
n = 4
arr[] = {1, -3, 5, -2}
k = 2
Here the answer will be,
1 => total sum = 1
-3 5 -2 => total sum = 0