算法帮助：如何将数组划分为N个段，且最大段最少（平衡分段）

我在一个俄语编程论坛上遇到了这个问题，但还没有想出一个优雅的解决方案。

Problem:

你有一个数组N 个正整数，你需要把它分成M 个连续段，使得最大段的总和是最小的可能值。我所说的段总数是指其所有整数的总和。换句话说，我想要一个平衡良好的数组分段，您不希望单个分段太大。

Example:

• 数组：[4,7,12,5,3,16]

• M = 3，这意味着我需要将数组分为 3 个子数组。

• 解决方案是： [4,7] [12, 5] [3, 16]，这样最大的段是 [3, 16] = 19，并且没有其他分段变体可以产生具有较小总数的最大段。

另一个例子：

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

解：[3, 13, 5] [7, 18] [8] [20, 1]，“最胖”的段是[7, 18] = 25（如果我错了请纠正，这个例子是我编的）

我有一种感觉，这是一些经典的 CS/数学问题，可能与某个名人的名字相关联，比如 Dijkstra 问题。 - 有没有已知的解决方案？ - 如果没有，除了暴力破解之外，你还能想出其他解决方案吗？据我所知，时间复杂度是这样的，指数。（N^M，更具体地说）。

预先感谢，stackoverflowers。

1. 让我们对答案进行二分搜索。

2. 为了得到固定的答案X很容易检查它是否可行（我们可以使用贪心算法（总是取最长的可能线段，使其总和为<= X）并将段数与M).

总时间复杂度为O(N * log(sum of all elements)).

这是一些伪代码

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