algorithm - 在随机生成的 bool 数组中，将 'k' false 更改为尝试创建最大的连续真值链

Question

我在面试中被问到以下问题:

在随机生成的 bool 数组中，例如:T F T T F F F T F F F F T

编写一个算法来确定将哪些假值更改为真值，以最大化最大的连续真值 block 。在上面的例子中，假设 k = 3。解决方案之一是:

T F T T T* T* T* T F F F F T

其中 T* 表示已更改的值。

除了简单的暴力破解，我想出的一种方法是找到最大的连续假值 block ，并将其与 k 进行比较。如果小于，则我们将整个 block 替换为 True 并继续剩余的“k”。然而，事实证明这种方法并不总能保证正确答案。

我想到的另一种更复杂的方法是:对于真实 block 之间的每个虚假 block ，计算通过翻转真实之间的虚假可以构建多大的 block 。然后归结为选择 true 之间的 block 的最佳组合来翻转。

这个问题的最优算法是什么？

非常感谢。

Answer 1

找到包含 k 个错误值的最大范围。您可以通过保持运行窗口在线性时间内完成此操作。