Longest sub array in rotating array

kbhavya1

Guys is there any way to find the longest subarray of 1's in log(n) time.

example

1- 110011111000 then the output is 5 from pos 5 to 10

2- 1110011101 the output here is 3 but after rotation 1 the array becomes

111100111 and the output is now 4.

3 - 001111 the output here is 4 from pos 3 to 6 but after rotation it becomes 3 from pos 4 to 6

Note: i found the longest subarray length in O(n) before rotation ... how can i improve the solution after rotation if i have the past results..

Nov 11 '18 #1

Rabbit

This is a weird question. Is this homework?

You can still do this in O(n). Just need a few extra variables. One for the length of the starting block. And one for the ending block that updates for each found block until you reach the end. Then you just need to check the last character to see if you need to subtract one from the end and add one to the start.

Nov 13 '18 #2