algorithm - 查找要翻转的位数以获得数组中的最大 1

Question

我们有如下的位数组

{1 0 1 0 0 1 0 1}

上面数组的位数是8

如果我们从 [1,5] 取范围，那么 [1,5] 范围内的位数是 [0 1 0 0 1].
如果我们翻转这个范围，那么翻转之后它将是 [ 1 0 1 1 0]
所以翻转 [1,5] 范围后 1 的总数是 [1 1 0 1 1 0 0 1] = 5

如果我们从 [1,6] 获取范围，那么 [1,6] 范围内的位数是 [0 1 0 0 1 0]。
如果我们翻转这个范围，那么翻转之后它将是 [ 1 0 1 1 0 1]
所以翻转 [1,5] 范围后 1 的总数是 [1 1 0 1 1 0 1 1] = 6

所以答案是 [1,6] 翻转之后我们可以得到 6 个 1 的数组

有没有好的算法可以解决这个问题。我只想到动态规划，因为这个问题可以分解成可以组合的子问题。

Answer 1

受@Nabbs 评论的启发，有一种在线性时间内解决此问题的简单方法:将问题简化为最大段和。

将所有 0 转换为 1，将所有 1 转换为 -1。那么这个问题就和变换后最小化数组的和一样了。 (最小和包含变换后数组中最多的-1，对应原问题中最多的1)。

我们可以计算总和为

sum(after flipping) = sum(non-flipped) - sum(flipped part before flipping)

因为翻转部分的和是倒过来的。如果我们现在将非翻转部分表示如下:

sum(non-flipped) = sum(original array) - sum(flipped part before flipping)

我们发现我们需要最小化

sum(after flipping) = sum(original array) - 2 sum(flipped part before flipping)

第一部分是常数，所以我们确实需要最大化翻转部分的总和。这正是最大段和问题的作用。

---

我写了一篇关于如何在线性时间内解决该问题的冗长推导 a while ago ，所以现在我只分享代码。下面我更新了代码以存储边界。我选择 javascript 作为语言，因为它很容易在浏览器中进行测试，而且我不必明确指定变量 x 和 y 的类型。

var A = Array(1, 0, 1, 0, 0, 1, 0, 1);
var sum = 0;

// count the 1s in the original array and
// do the 0 -> 1 and 1 -> -1 conversion
for(var i = 0; i < A.length; i++) {
    sum += A[i];
    A[i] = A[i] == 0 ? 1 : -1;        
}

// find the maximum subarray
var x = { value: 0, left: 0, right: 0 };
var y = { value: 0, left: 0 };
for (var n = 0; n < A.length; n++) {
    // update y
    if (y.value + A[n] >= 0) {
        y.value += A[n];
    } else {
        y.left = n+1;
        y.value = 0;
    }
    // update x
    if (x.value < y.value) {
        x.left = y.left;
        x.right = n;
        x.value = y.value;
    }
}

// convert the result back
alert("result = " + (sum + x.value) 
    + " in range [" + x.left + ", " + x.right + "]");

您可以在浏览器中轻松验证这一点。例如在 Chrome 中，按 F12，单击控制台并粘贴此代码。它应该输出

result = 6 in range [1, 4]