Length of the longest sub-array which consists of all '1'

Question

suppose i have a list say x=[1,0,0,1,0,1,1,1,0,1,1,0].Here longest sub-array which have continuous 1 is of length 3. I have a o(n) approach but can it be done in o(logn) using segment tree and how? I am practicing problems based on segment tree and am curious how to approach this i want to cut down the complexity.

a=[1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0]
size=len(a)
counter=0
lis=[]
for _ in range(size):
    if a[_]==1:
        counter+=1
    else:
        lis.append(counter)
        counter=0
print(max(lis))

Answer 1

In general case, you cannot do better than O(n): let's suppose that we have

[0, 0, 0... 0, 1, 0 ... 0]

all zeros and one 1. In order to distinguish it from all zeroes case you have to find out the only 1 - you have to scan the entire list, since 1's position can be arbitrary.

If you are given an algorithm with better than O(n) time complexity it's easy to create a counter example. Run the algorithm on the all zeroes case. Since the algorithm is better than O(n), it can't check all the items of the list. Change one of these skipped items into 1 and run the algorithm again.

Answer 2

As Dmitry Bychenko points out, you cannot improve on the algorithmic time complexity, but for the case at hand, the usage of some C-optimized utils over a plain Python loop can speed things up:

from itertools import groupby

a = [1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0]
m = max(sum(g) for k, g in groupby(a) if k == 1)