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

c++ arrays algorithm dynamic-programming subset-sum
user3778989 picture user3778989 · Sep 24, 2016 · Viewed 26.2k times · Source

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

Saeid picture Saeid · Sep 24, 2016

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).

Related questions

Searching in a sorted and rotated array

While preparing for an interview I stumbled upon this interesting question: You've been given an array that is sorted and then rotated. For example: Let arr = [1,2,3,4,5], which is sorted Rotate it twice to the right to give [4,5,1,2,3]. Now how best …

Read More
What is the safe way to fill multidimensional array using std::fill?

Here is what I am using: class something { char flags[26][80]; } a; std::fill(&a.flags[0][0], &a.flags[0][0] + 26 * 80, 0); (Update: I should have made it clear earlier that I am using this inside a class.)

Read More
Faster than binary search for ordered list

is there an algorithm that is faster than binary search, for searching in sorted values of array? in my case, I have a sorted values (could be any type values) in an A array, I need to return n if …

Read More