最小化 0/1 数组中的最大连续子数组

Question

算法题

给定
的 0/1 的二进制数组 在一次操作中，我可以翻转数组的任何数组[索引]，即 0->1 或 1->0 所以目标是通过使用最多 k 个翻转来最小化连续 1 或 0 的最大长度

例如，如果 11111 if array 和 k=1 ，最好将 array 设置为 11011
并且最大连续1或0的最小值为2

对于 111110111111 和 k=3 ans 是 2

我尝试了 Brute Force（通过尝试各种位置翻转）但效率不高

我觉得贪心，但想不通
你能帮我做算法吗，O(n) 或类似的

Answer 1

可以通过按顺序读取每个位并将每个连续的 1 组的大小记录到列表 A 中来设计解决方案。

填完 A 后，您可以按照下面伪代码所述的算法进行操作：

result = N
for i = 1 to N
    flips_needed = 0
    for a in A:
        flips_needed += <number of flips needed to make sure largest group remaining in a is of size i>
    if k >= flips_needed:
        result = flips_needed
        break
return result

N是整个初始序列的位数。

上述算法的工作原理是将 1 的组分成最多 i 的大小。每当这样做需要 <= k 时，我们就会得到我们正在寻找的结果，因为 i 从 1 开始上升。（即，当我们发现 flips_needed <= k 时，我们知道 1 的组已尽可能少）

最小化 0/1 数组中的最大连续子数组

minimize the maximum continious subarray in array of 0/1

greedy