将数组划分为最大数量的组

Question

只有一个规则可循：每组的总和应大于或等于其右侧的组。

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

例如数组14 13 2 11

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

你觉得我的猜测是真的吗？如果没有，你有其他解决问题的方法吗？

Answer 1

这是一个 O(n^2) 时间算法，其中 n 是数组的长度。我收回我的评论，即 "probably" 更快。

有一个更简单的 O(n^4) 时间算法可以说明动态规划的主要思想。我们准备 table 个条目 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) table 个条目，我们计算了 O(n) 个总和的最大值，每个 O(n) 个项目。

我们做了两处优化。第一个很简单：随着我们 h 的变化，逐步更新总和 S(h, i)。这将成本降低到 O(n^3)。我们可以对 S(i, j) 执行相同的操作，但假设我们明智地将其提升到最大循环之外，还没有任何效果。

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

Partitioning an array to maximal number of groups