将数组分区为最大组数

这是一个O(n^2)-time算法，其中n是数组的长度。我撤消我的评论，即“可能”有一个更快的评论。

有一个更简单的O(n^4)时间算法，它说明了动态程序的主要思想。我们准备一个条目表，T(i, j)其中i, j条目包含最大数目的组，[0, j)可以将被索引的数组元素适当地分组到其中，以使最后一组具有索引[i, j)。

我们有复发

T(0, j) = 1 for all j
T(i, j) =          max          T(h, i) + 1,
          h : S(h, i) ≥ S(i, j)

其中S(i, j)是索引的数组元素的总和[i, j)，并且空的最大值被视为负无穷大。答案是

max T(i, n).
 i

我们得出结论，O(n^4)因为对于O(n^2)表条目，我们计算O(n)每个O(n)项目的总和的最大值。

我们进行了两个优化。第一个很容易：S(h, i)随着我们的变化，逐渐增加总和h。这将成本降低到O(n^3)。我们可以对进行相同的操作S(i, j)，但是如果我们明智地将其从max循环中吊起，则没有任何效果。

第二个取决于非负条目。特别是i, j，有效集h是一个类似的间隔[0, k)，可能为空。对于i固定和j递减，总和S(i, j)不增加，因此间隔不会缩小。这意味着我们也可以递增地更新最大值，从而产生O(n^2)-time算法。