arrays - 圆形阵列中的最大子段数

Question

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

例如: n = 6 m = 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 .然后增加 B而 F 之间的总和和 B大于 m (但当 is 仍然大于或等于 m 时停止)。
2. 更新数组:L[F] = 1 + L[B] , S[F] = S[B] .
3. 在 F<n 时重复步骤 1,2 .在增加 F 的同时在第 1 步中，将最近更新的值复制到 L[F]和 S[F] .
4. 重置F归零。
5. 增量F F 之前的元素总和在 B 之后小于 m .然后增加 B while 之前求和F在 B 之后大于 m (但当 is 仍然大于或等于 m 时停止)。
6. 如果F <= S[B]使用 L[B] + 1更新子分段的最大数量。
7. 在 B<n 时重复步骤 5,6 .