python - 所有 '1'组成的最长子数组的长度

Question

假设我有一个列表 x=[1,0,0,1,0,1,1,1,0,1,1,0]。这里是最长的子数组连续 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]

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

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