由所有'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))

- Om Sharma

---

你在两种情况下都使用列表吗？构建线段树至少需要 O(n) 的时间。 - Patrick Haugh

列表中只有两个数字（0和1）吗？ - Sniper

最坏情况肯定是O(n)。平均情况可能就不一样了。 - Paul Panzer

如果您在遍历列表时知道当前的最大值，并且在l[n]处得到了一个1，则可以检查l[n+maximum]。如果该值为0，则知道l[n]处的运行不大于maximum，并且可以从l[n+maximum+1]继续前进，跳过列表的一部分。如果l[n+maximum]是1，则必须从l[n+1]继续前进。尽管如此，这仍然是一个O(n)算法。 - Patrick Haugh

你为什么想要复杂性？你的代码可以进行很多优化。你想要优化的代码还是更好的时间复杂度？ - Sniper

Answer 1

通常情况下，您无法做得比 O(n) 更好：假设我们有

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

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

如果给定的算法时间复杂度优于O(n)，那么就容易创建一个反例。在全零情况下运行算法。由于该算法优于O(n)，它无法检查列表的所有项。将其中一个被跳过的项更改为1并再次运行算法。

- Dmitry Bychenko

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)

- user2390182

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（最大值）为4。

- Joe Iddon

---

我已经做过了。我在评论中提到了它。但这并没有快多少。 - Om Sharma

@OmSharma 抱歉，我错过了。我非常确定这已经是最快的速度了。据我所知，没有其他方法可以提高效率。 - Joe Iddon

我遇到的问题是可能有N个查询来查找最长子数组，而N可能会很大，高达（10**9）。虽然对于1个查询或者1000个查询程序运行速度很快，但是对于大量查询则变得很慢。 - Om Sharma

当所有元素都为1时，例如[1, 1, 1]，期望输出为3，但实际输出为0。在循环后添加m = max(c, m)。 - Dmitry Bychenko

@OmSharma 你会为每一个N的查询读取整个列表吗？ - Sniper

Answer 4

如何将一个包含数字的字符串按照零分割，并找出结果元素中最长的长度。

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

- srikavineehari

---

可以使用 bytes 来替代，更短更快：len(max(bytes(a).split(b'\0'))). - Stefan Pochmann