arrays - 获取最长连续的 1 序列

Question

我最近遇到了一个问题陈述它说:

Given an array of 0s and 1s, find the position of 0 to be 
replaced with 1 to get longest continuous sequence of 1s.

For example : Array- 1,1,0,0,1,0,1,1,1,0,1,1,1
Output - index 9

我尝试了一种蛮力方法，用 1 替换每个遇到的 0，在每次这样的替换之后，我计算了 1 的最大连续重复序列并每次更新它。

是否有更好的方法/算法来解决这个问题？

Answer 1

应该有一个一次性的解决方案。总体思路是数一数，然后将每个零的长度加起来。好吧，不是每个零，只是最后遇到的一个和最长的。

您需要跟踪两件事:

• 迄今为止最长的链。
• 前一个零值，以及前面零值的长度。

流程如下:

1. 开始遍历字符串，直到遇到零。随时记录人数。

2. 当你击中零时，记住零的位置以及前面 1 的数量。

3. 将 1 数到下一个零。

4. 回到之前的零，将新的“一”加到之前的“一”上。如果这比最长的链长，则替换最长的链。

5. 记住这个零和前面的 1。

6. 重复直到到达字符串的末尾。

7. 然后在字符串的末尾，返回并将长度添加到前一个零，并在适当的情况下替换最长的链。