arraysalgorithmsegments

Maximum number of subsegments in a circle array

There are n positive numbers (A1 , ... An) on a circle, how do we divide this circle into subsegments with sum greater or equal to m so that number of subsegments are maximum in O(n) , or O(nlogn)

eg : n = 6 m = 6

3 1 2 3 6 3

ANS = 3 since we can divide the array into three subsegments{[2,4],[5,5],[6,1]}

Solution

  • If there is at least one number greater or equal to m in the array, just cut the array into smallest possible pieces starting from one of these numbers. Otherwise (and if sum of numbers is at least 2*m) use a pointer-chasing algorithm.

    This algorithm uses 2 additional arrays: L for chain lengths (initially zero) and S for starting indices (initially equal to own indices: 0, 1, 2, ...). And 2 array indices: F and B (initially zero).

    1. Increment F while sum between F and B is less than m. Then increment B while sum between F and B is greater than m (but stop when is is still greater or equal to m).
    2. Update arrays: L[F] = 1 + L[B], S[F] = S[B].
    3. Repeat steps 1,2 while F<n. While incrementing F on step 1, copy most recently updated values to L[F] and S[F].
    4. Reset F to zero.
    5. Increment F while sum of elements before F and after B is less than m. Then increment B while sum before F and after B is greater than m (but stop when is is still greater or equal to m).
    6. If F <= S[B] use L[B] + 1 to update maximum number of subsegments.
    7. Repeat steps 5,6 while B<n.