圆形阵列中的最大子段数

Question

一个圆上有n个正数(A1 , ... An)，如何把这个圆分成和大于等于m的子段，使得子段数在O(n)内最大，或 O(nlogn)

例如： n = 6 米 = 6

3 1 2 3 6 3

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