找到要翻转的位数,以便在数组中获得最大值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)

第一部分是常数,所以我们真的需要最大化翻转部分的总和.这正是最大段总和问题所做的.

我写了一篇关于如何解决线性时间问题,一个漫长的推导前一阵子,所以现在我只共享代码.下面我更新了代码以存储边界.我选择了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]

Answer 2

该解决方案使用 Kadane 算法。

我们必须选择具有最大数量 0 和最小数量 1 的子字符串，即具有 max(count(0)-count(1)) 的子字符串。这样在翻转之后，我们可以在最终字符串中获得最大数量的 1。

遍历字符串并保持计数。每当我们遇到 0 时增加这个计数，遇到 1 时减少它。具有这个计数最大值的子字符串将是我们的答案。

这是 alGOds 的一个视频，它很好地解释了这种方法。如果您有任何疑问，请务必观看。

链接：https : //youtu.be/cLVpE5q_-DE