Algorithm help: how to divide array into N segments with least possible largest segment (balanced segmenting)

Question

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.

Answer 1

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;
}