圆形数组中子段的最大数量

Question

有n个正数（A1，...An） 在一个圆上，我们如何将这个圆划分为总和大于或等于 m 的子段，以便子段数在 O（n） 或 O（nlogn） 中最大

例如：n = 6 m = 6

3

1 2 3 6 3

ANS = 3因为我们可以将数组分为三个子段{[2,4]，[5,5]，[6,1]}

Answer 1

如果数组中至少有一个大于或等于 m 的数字，只需从其中一个数字开始将数组切成尽可能小的片段。否则（如果数字之和至少为2*m）使用指针追踪算法。

此算法使用 2 个附加数组：L 用于链长度（最初为零），S 用于起始索引（最初等于自己的索引：0、1、2、...）。和 2 个数组索引：F 和 B（最初为零）。

递
1. 增F而 F 和 B 之间的总和小于 m 。然后在 F 和 B 之间的总和大于 m 时递增B（但在 is 仍然大于或等于 m 时停止）。
2. 更新数组：L[F] = 1 + L[B]、S[F] = S[B]。
3. 重复步骤 1,2 F<n 。在步骤 1 上递增F时，将最近更新的值复制到 L[F] 和 S[F] 。
4. 将F重置为零。
5. F递增，而F之前和之后的元素之和B小于 m 。然后在 F 之前和之后的总和大于 B m 时递增B（但在 is 仍然大于或等于 m 时停止）。
6. 如果F <= S[B]请使用L[B] + 1更新最大子分段数。
7. 重复步骤 5,6，同时B<n。