Divide array into k contiguos partitions such that sum of maximum partition is minimum

Question

Here maximum sum subset is one of k subsets that give maximum sum e.g: arr = [10,5,3,7] and k = 2 possible ways to divide arr in k subsets is

  {10,[5,3,7]},{[10,5],[3,7},{[10,5,3],7}

and

{[10,5],[3,7} is the optimal one.

Edit: it is equivalent of https://www.codechef.com/DI15R080/problems/MINMAXTF

Answer 1

Assume you know the answer is x which means sum of the maximum subset is equal to x. You can verify this assumption by a greedy algorithm O(n). (Traverse the array from left to right and pick items until the sum of that subset is lower than x). Now you can binary search on x and find the minimum value for x. The complexity of this algorithm is O(nlogn).

Answer 2

This is an example of binary searching the sample space.

int min_max_sum(std::vector<int> & a, int K) {        

    int n = a.size();    
    long long high = 0, low = 0, mid = 0;

    for (int i = 0; i < n; ++i) {
        high += a[i];
        low = max(a[i], low);
    }

    while(low <= high) {
        mid = (low+high)/2;

        long long part_sum = 0;
        int parts = 1;
        for (int i = 0; i < n; ++i) {
            if (part_sum + a[i] > mid) {
                part_sum = 0;
                parts++;
            } else {
                part_sum += a[i];
            }
        }

        // if no. of parts in less than (or equal to) K then mid needs to (,or can) be more constrained by reducing upper limit
        if (parts <= K) {
            high = mid - 1;
        } else { 
            low = mid + 1;
        }
    }

    return mid;
}

complexity : O(n log(sum(array))).

But since logrithms are exponentially better than linears, this complexity is quite good.

worst case complexity : O(n log(INT_MAX * n))=O(32 n +n log(n))=O(n log(n)).

Answer 3

Lets start with an example. Suppose N=5 and k=3(assuming that there will be three parts after division).Let our array be {1,2,8,4,9}. We can observe that if k was equal to 1, then sum of maximum partition would be sum(all array elements) i.e., 24 and if k=5, then sum of maximum partition would be max(all array elements) i.e, 9. Now, we can observe that as k increases, sum of maximum partition's minimum value decreases. Our algorithm will take the help of binary search in doing so. But how to do it????? By looking at the question-we can see, we have to find the minimum of maximum which arouses the feeling of problems like- "FFFFTTTTTTTT" where we have to find the first T. We are going to do exactly the same stuff but will take the help of a function in doing so.(Look at the code and answer from here, parallelly)..The helper function will find the value of K when the minimum sum of maximum partition is provided.We will initialize low=max(all array elements),here low=9 and high=sum(all array elements)i.e.,high=24.Therefore,mid=16,So,for min_max_dist=16,our helper function will return the number of k required.If number of k>K,it means that our min_max_dist can accommodate more values in it.So,we will increment our low value to mid+1 and if number of k<=K, it means that in less number of partition,we can achieve that min_max_dist,,but we can do more partition and therefore we can decrease high value to mid.So,our code will execute on our example in following way:-

    low           high               mid       number_of_k
    9             24                 16         9
    9             16                 12         2
    9             12                 10         4
    11            12                 11         3

and finally our result->low=11 will be returned..

    #include <bits/stdc++.h>
    #define ll long long int
    using namespace std;

    ll number_of_k(ll arr[],ll n,ll minimum_max__dist){
       ll sum=0;
       ll k=1;
       for(ll i=0;i<n;i++){
          sum+=arr[i];
         if(sum > minimum_max__dist){
           sum=arr[i];
            k++;
          }
      }
    return k;
   }

    ll Max(ll arr[], ll n)
    {
       ll max1 = -1;
       for (ll i = 0; i < n; i++)
          if (arr[i] > max1)
              max1 = arr[i];
      return max1;
    }

    ll Sum(ll arr[], ll n)
    {
      ll sum = 0;
       for (int i = 0; i < n; i++)
       sum += arr[i];
       return sum;
     }

       ll min_max_bin_search(ll arr[],ll n,ll k){
         ll low=Max(arr,n);
         ll high=Sum(arr,n);
         ll mid;
while(low<high){
     mid=low+(high-low)/2;
    if(number_of_k(arr,n,mid)<=k)
       high=mid;
    else
        low=mid+1;
     }
  return low;
  }


 int main()
 {
      ll n,k;
       cin>>n>>k;
       ll arr[n];
       for(ll i=0;i<n;i++)cin>>arr[i];
       cout<<min_max_bin_search(arr,n,k)<<endl;

   return 0;
 }

Time complexity of this algorithm is->O(nlogn)

Read this article on Binary Search-> https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/ and Solve this problem-> http://www.spoj.com/problems/AGGRCOW/