The length of the longest sub-matrix, 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] . The longest subarray, which has continuous 1, has a length of 3. I have an o (n) approach, but can this be done in o(logn) using a segment tree and how? I deal with problems based on the segment tree, and I'm curious how to approach this, I want to reduce 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 the general case, you cannot do better than O(n) : suppose we have

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

all zeros and one 1 . To distinguish it from all zeros, you need to find out only 1 - you need to scan the entire list, since position 1 can be arbitrary.

If you are given an algorithm with more complex complexity O(n) , it is easy to create an example counter. Run the algorithm in all cases of zeros. Since the algorithm is better than O(n) , it cannot check all the elements of the list. Change one of these missing elements to 1 and run the algorithm again.

Answer 2

As Dmitry Bychenko noted , you cannot improve the algorithmic complexity in time, but for the case under consideration, the use of some utles optimized for C-utilities over the Python Contour plain can speed up the work:

 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) 

Answer 3

This solution should be faster as it removes the slow addition to list .

 a = [1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0] m = c = 0 for i in a: if i: c += 1 else: m = max(c, m) c = 0 m = max(c, m) 

which gives m (max) as 4 .

Answer 4

How about splitting the string of all numbers at zero and finding the length max resulting elements.

 >>> a_list = [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0] >>> max(''.join(map(str, a_list)).split('0')) '1111' >>> len(max(''.join(map(str, a_list)).split('0'))) 4 >>> ones = [1, 1, 1] >>> max(''.join(map(str, ones)).split('0')) '111' >>> len(max(''.join(map(str, ones)).split('0'))) 3 

Edit : I like that Stefan Pohmann replies in the comments here: len(max(bytes(a_list).split(b'\0')))