给定颜色的最长序列

Question

假设我们有一个元素列表，其值是黑白的。是否有 O(N) 算法来找到由黑色元素组成的最长序列？

我知道使用二进制搜索我们可以在 O(Nlog(N)) 上完成。我想知道我们是否可以做得更好。

Answer 1

我觉得我可能误解了这个问题，但是：按顺序逐一浏览它们？

Answer 2

您可以保留数组的第一个值和它的索引。并分配 maxCount 和 maxIndex 以保持最长序列开始的位置。

Create oldValue and assign first value of array 
Create maxCount variable
Create maxIndex variable (it should be 0 because we use first value of array)

Move on array - start with 2nd element (because we used first already)
   if new value is equal old value
      go to next element and increase count
   else
      check if count > maxCount
         if so maxCount = count and maxIndex = i
         else count = 0 
   and oldValue = currentValue

这样做直到到达数组的末尾。也是O(N)。我不写任何代码，因为我相信你应该自己做。试过之后有什么想问的。

Answer 3

我认为 Kadane 的算法会在最佳时间为您提供解决此问题的方法。考虑包含您的 'Black' 和 'Whites' 的 ListItems，因此对于一个实例，我们会跟踪到目前为止我们连续计算了多少 'Black' 项目，如果我们遇到 'White' 比我们将我们的计数器重置为零，并且如果在任何时候，我们的元素 'Black' 或 'White' 的计数超过了全局最大计数，那么我们用本地计数更新全局计数。

我已经在 python 中进行了编码，欢迎大家提出意见和修改。我是 Whosebug（和编码）的新手。

另外，大家可以去查查here and here，以便更好地理解。

ListItems = ['Black', 'White', 'Black', 'Black', 'White', 'White', 'White', 'White','Black','Black','Black','Black', 'White', 'White','Black', 'White', 'White','Black','Black', 'White', 'White']


maxi = 0
max_so_far = 0

for i in ListItems:
  if i =='Black':
    maxi += 1

  else:
    maxi = 0 

  if maxi > max_so_far:
    max_so_far = maxi

print(max_so_far)

给定颜色的最长序列

Longest sequence with given color

algorithm

list

binary-search