8

I came across this problem on one of the russian programming forums, but haven't come up with an elegant solution.

Problem:

You have an array with N positive integers, you need to divide it into M contiguous segments, so that the total of the largest segment is the smallest possible value. By segment's total, I mean the sum of all its integers. In other words, I want a well-balanced array segmentation, where you don't want a single segment to be too large.

Example:

  • Array: [4, 7, 12, 5, 3, 16]

  • M = 3, meaning that I need to divide my array into 3 subarrays.

  • Solution would be: [4,7] [12, 5] [3, 16] so that the largest segment is [3, 16] = 19 and no other segmentation variant can produce the largest segment with smaller total.

Another example:

  • Array [3, 13, 5, 7, 18, 8, 20, 1]
  • M = 4

Solution: [3, 13, 5] [7, 18] [8] [20, 1], the "fattest" segment is [7, 18] = 25 (correct me if I am wrong, I made up this example)

I have a feeling that this is some classic CS/math problem, probably with some famous person's name associated with it, like Dijkstra's problem. - Is there any known solution for it? - If not, can you come up with some other solution besides brute forcing, which is, as far as I understand time complexity, exponential. (N^M, to be more specific).

Thanks in advance, stackoverflowers.

Improve this question
6
  • This question would be a better fit for Programmers Stack Exchange. Commented Jan 22, 2015 at 18:03
  • 6
    @Jordan why? The StackOverflow help says you can ask about a software algorithm. The Programmers help says you can ask about algorithm and data structure concepts. I could see this question fitting either site. Commented Jan 22, 2015 at 18:07
  • If this is a homework question you should show some code and basic own research (as of site definition). It does sound like the knappsack problem, btw. Commented Jan 22, 2015 at 18:27
  • 1
    sounds like the painters problem: leetcode.com/2011/04/the-painters-partition-problem.html Commented Jan 22, 2015 at 20:16
  • 1
    @eckes It is probably a variation of knapsack problem. Commented Jan 23, 2015 at 5:48

2 Answers 2

Reset to default
5

  1. Let's do a binary search over the answer.

  2. For a fixed answer X it is easy to check if it is feasible or not(we can just use a greedy algorithm(always taking the longest possible segment so that its sum is <= X) and compare the number of segments to M).

The total time complexity is O(N * log(sum of all elements)).

Here is some pseudo-code

boolean isFeasible(int[] array, long candidate, int m) {
    // Here goes the greedy algorithm.
    // It finds the minimum number of segments we can get(minSegments).
    ...
    return minSegments <= m;
}

long getMinimumSum(int[] array, int m) {
    long low = 0; // too small
    long high = sum of elements of the array // definitely big enough
    while (high - low > 1) {
         long mid = low + (high - low) / 2;
         if (isFeasible(array, mid, m))
             high = mid;
         else
             low = mid;
    }
    return high;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Could you please expand on your answer? I didn't uderstand the binary part, array isn't sorted and isn't allowed to be.
Nice. A minor optimisation: if you ever find yourself trying a value X that is less than SUM/M, you can skip the O(N) greedy pass for that iteration and immediately conclude that that X is too low, since in any partition of SUM into M parts, there must be at least one part >= SUM/M.
How do you show that the greedy algorithm is optimal?
2

I like ILoveCoding's approach. Here's another way that takes O(MN^2) time, which will be faster if N and M are small but the numbers in the array are very large (specifically, if log(sum) >> MN, which is possible but admittedly doesn't sound very realistic). It uses dynamic programming.

Let's consider partitioning just the subarray consisting of the first i <= N entries into j <= M segments. Let f(i, j) be the weight of the largest segment in the best solution for this subproblem -- i.e. the weight of the largest segment in that j-partition of the first i numbers whose largest segment is smallest among all such partitions. We want to compute f(N, M), as well as a (there may be more than one) partition that corresponds to it.

It's easy to compute f(i, 1) -- that's just the sum of the first i elements:

f(i, 1) = x[1] + ... + x[i]

To compute f(i, j) for j >= 2, observe that element i must be the final element of some segment that starts at some position 1 <= k <= i, and which is preceded by j-1 segments -- and in any optimal solution for parameters (i, j), those j-1 preceding segments must themselves be optimal for parameters (k-1, j-1). So if we consider every possible start position k for this final segment and take the best, we will calculate the best j-partition of the first i elements:

[EDIT 3/2/2015: We need to take the max of the new segment and the largest remaining segment, instead of adding them!]

f(i, j >= 2) = minimum of (max(f(k-1, j-1), x[k] + ... + x[i])) over all 1 <= k <= i

If we try k values in decreasing order, then we can easily build up the sum in constant time per k value, so calculating a single f(i, j) value takes O(N) time. We have MN of these values to compute, so the total time needed is O(MN^2).

One more boundary condition is needed to forbid trying to partition into more segments than there are elements:

f(i, j > i) = infinity

Once we have calculated f(N, M), we could extract a corresponding partition by tracing back through the DP matrix in the usual way -- but in this case, it's probably easier just to build the partition using ILoveCoding's greedy algorithm. Either way takes O(N) time.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.