Longest sub array in rotating array

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • kbhavya1
    New Member
    • Nov 2018
    • 1

    Longest sub array in rotating array

    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..
  • Rabbit
    Recognized Expert MVP
    • Jan 2007
    • 12517

    #2
    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.

    Comment

    Working...