由“1”组成的最长子阵列的长度

Question

假设我有一个列表说x=[1,0,0,1,0,1,1,1,0,1,1,0].Here最长的子阵列，连续1长度为3.我有一个o（n）方法，但可以使用分段树在o(logn)完成，如何？我正在练习基于分段树的问题，我很好奇如何处理这个我想减少复杂性。

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

一般情况下，你不能做得比O(n)更好：让我们假设我们有

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

全零和一个1。为了将它与全零区分开，你必须找出唯一的1 - 你必须扫描整个列表，因为1的位置可以是任意的。

如果给出一个优于O(n)时间复杂度的算法，则很容易创建一个计数器示例。在全零情况下运行算法。由于该算法优于O(n)，因此无法检查列表中的所有项目。将其中一个跳过的项目更改为1并再次运行算法。

Answer 2

正如Dmitry Bychenko指出的那样，你无法改进算法的时间复杂度，但对于手头的情况，使用一些C优化的工具比普通的Python循环可以加速：

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

这个解决方案应该更快，因为它消除了慢慢附加到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)

这使m（max）成为4。

Answer 4

如何将所有数字的字符串拆分为零并找到结果元素的max长度。

>>> 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

编辑：我在这里的评论中喜欢Stefan Pochmann的回答：len(max(bytes(a_list).split(b'\0')))