Divide array into k contiguos partitions such that

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

You can find a good writeup about dynamic programming based solution here: https://www.geeksforgeeks.org/painters-partition-problem/ and It's complexity is O(k*N^2).

To get a better solution, you can use the binary search method as suggested by others. You can find a more detailed solution that uses binary search here: https://www.geeksforgeeks.org/painters-partition-problem-set-2/ and it's complexity is O(NlogN)

Answer 2

The division is just a brute force problem. You have to focus to the function to minimize. So what you have to minimize is the deviation from the average.

int sum_arr(int *arr,int size)
{
    int res=0;
    while (size-->0)
       res+=*arr++;
   return res;
}
int   minimize( const int *array, int size)
{
    int i,j,cur_i;
    double dev, cur_min,avg=(double)sum_arr(array,size)/size;

    for (i=1;i<size-1;i++)
      {
         dev=abs(avg-sum_arr(array,i));
         dev+=abs(avg-sum_arr(array+i,size-i);
         if (dev<cur_min)
         {
              cur_min=dev;
               cur_i=i;
         }
      }
     return cur_i;
}

A simple code would be:(Not tested)

Answer 3

This is an example of binary searching the sample space.

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


    int n=a.size();

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

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

        long long part_sum=0;
        int parts=0;
        for (int i = 0; i < n; ++i)
        {
            if (part_sum+a[i]>mid)
            {
                part_sum=0;
                parts++;
            }else{
                part_sum+=a[i];
            }
        }
        if (parts<k)
        {
            low=mid+1;
        }else{ //if we have got exactly k parts or more, keep on decreasing the value of sum of subarray
            high=mid-1;
        }
    }

    return high;
}

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 4

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 5

This can be solved using dynamic programming:

Lets define first DP[n,m] to be the optimal solution for dividing the subarray C[1..n] into m parts. Where each part has at least one element.

DP[n,1] = sum(C1:Cn)
DP[n,n] = max(C1:Cn)
DP[n,m] = min( sum(Ck:Cn) + DP[k-1,m-1] )
          where k goes from m to n

Explanation:
DP[n,1] - Base case, when the number of partitions is 1 there is only one way - all elements left (from 1 to n).
DP[n,n] - Whenever the number of partitions are equal to the number of elements left in the array there is only one legal way to divide it - each element in a different partition, so the partition with the maximum sum is the maximum element in the array.
DP[n,m] - This is the main solution. We don't know exactly how many elements will be our next partition, so we need to go over all options and get the minimum from it.

Answer 6

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/