algorithm - 将数组分区为最大组数

Question

只有一条规则要遵循：每个组的总和应该大于或等于它右侧的组。

我的猜测是构建一个包含所有分区选项的树，然后递归回溯。

例如，数组 14 13 2 11

结果：3. 3 个组（{14}、{13}、{2、11}）

你认为我的猜测是真的吗？如果没有，您还有其他解决问题的方法吗？

Answer 1

这是一个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)，但假设我们明智地将其提升到最大循环之外，还没有任何效果。

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