发现有相同数量的1和0的最大子二进制套 [英] Finding the maximum subsequence binary sets that have an equal number of 1s and 0s

问题描述

我在互联网上找到以下问题，并想知道我怎么会去解决它：

  

您给出含0和1的阵列。寻找O（n）时间及O（1）空间算法来找到最大的子序列具有相同数量的1和0。

     

例如：

     

  
1. 10101010 -   最长的子序列中满足的问题是输入本身
  
2. 1101000 -   最长的子序列中满足问题是110100
  

解决方案

更新

我要彻底改写我的答案。 （如果你已经upvoted的早期版本，那么，你被骗！）

再次让我们总结一下简单的情况下，把它弄出来的方式：

  

查找最长的 $ P $含PFIX 的比特串   相等数目的1和0的   数组。

这是微不足道的：一个简单的计数器是必要的，我们计算多少1S比0，而迭代的比特串，同时保持这一点。其中，该计数器变为零，最后一次的位置是最长的追捧preFIX结束。 O（N）时间，O（1）空间。 （我完全相信到现在，这是最初的问题问什么。）

现在让切换到更困难的版本问题：我们不再需要的子序列是prefixes - 他们可以从任何地方开始

在一些来回想，我想可能没有这个线性算法。例如，考虑preFIX111111111111111111 ...。每单1这些可能是最长的子序列的开始，没有候选人子起始位置占主导地位（即总给人不是更好的解决方案）的任何其它位置，因此我们不能丢掉任何人（O（N）空间），在任何步骤，我们必须能够选择最佳开局的（有相同数量的1和0的当前位置）出直线很多考生，在O（1）时间。 事实证明这是可行的，然后轻松地可行的事，因为我们可以选择以1秒的运行总和（+1）和0（-1），这至多有大小N候选人，我们可以保存我们到达2N单元，每个单元总和第一的位置 - 见下文PMOD的答案（yellowfog的意见和几何的洞察力太）

未能发现这一招，我已经更换了快，但错缓慢但确定算法，（因为正确的算法是preferable错误的人！）：

• 在创建数组 A 以1s的累计数从一开始到那个位置，如如果位串是001001001，那么该阵列将是[0，0，1，1，1，2，2，2，3]。利用这一点，我们可以在O测试（1）是否有子（I，J），包容性，是有效的：的isValid（I，J）=（j - 我+ 1 = = 2 *（A [j]的 - A [1 - 1]），也就是说，它是有效的，如果它的长度是1秒的两倍它的量。例如，子序列（3,6）是有效的，因为6 - 3 + 1 == 2 * A [6] - A [2] = 4

• 普通老式双循环：

  maxSubsLength = 0 对于i = 1至N - 1   对于j = 1 + 1至N     如果isValid方法（I，J）... #maintain maxSubsLength   结束 结束

这可以使用一些可以加快一点分支定界跳过这比当前maxSubsLength缩短I / J，序列，但渐进这仍然是为O（n ^ 2）。慢，但在其一侧一大利好：正确！

I found the following problem on the internet, and would like to know how I would go about solving it:

You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space algorithm to find the maximum sub sequence which has equal number of 1s and 0s.

Examples:

1. 10101010 - The longest sub sequence that satisfies the problem is the input itself
2. 1101000 - The longest sub sequence that satisfies the problem is 110100

解决方案

Update.

I have to completely rephrase my answer. (If you had upvoted the earlier version, well, you were tricked!)

Lets sum up the easy case again, to get it out of the way:

Find the longest prefix of the bit-string containing an equal number of 1s and 0s of the array.

This is trivial: A simple counter is needed, counting how many more 1s we have than 0s, and iterating the bitstring while maintaining this. The position where this counter becomes zero for the last time is the end of the longest sought prefix. O(N) time, O(1) space. (I'm completely convinced by now that this is what the original problem asked for. )

Now lets switch to the more difficult version of the problem: we no longer require subsequences to be prefixes - they can start anywhere.

After some back and forth thought, I thought there might be no linear algorithm for this. For example, consider the prefix "111111111111111111...". Every single 1 of those may be the start of the longest subsequence, there is no candidate subsequence start position that dominates (i.e. always gives better solutions than) any other position, so we can't throw away any of them (O(N) space) and at any step, we must be able to select the best start (which has an equal number of 1s and 0s to the current position) out of linearly many candidates, in O(1) time. It turns out this is doable, and easily doable too, since we can select the candidate based on the running sum of 1s (+1) and 0s (-1), this has at most size N, and we can store the first position we reach each sum in 2N cells - see pmod's answer below (yellowfog's comments and geometric insight too).

Failing to spot this trick, I had replaced a fast but wrong with a slow but sure algorithm, (since correct algorithms are preferable to wrong ones!):

• Build an array A with the accumulated number of 1s from the start to that position, e.g. if the bitstring is "001001001", then the array would be [0, 0, 1, 1, 1, 2, 2, 2, 3]. Using this, we can test in O(1) whether the subsequence (i,j), inclusive, is valid: isValid(i, j) = (j - i + 1 == 2 * (A[j] - A[i - 1]), i.e. it is valid if its length is double the amount of 1s in it. For example, the subsequence (3,6) is valid because 6 - 3 + 1 == 2 * A[6] - A[2] = 4.

• Plain old double loop:

  maxSubsLength = 0 for i = 1 to N - 1 for j = i + 1 to N if isValid(i, j) ... #maintain maxSubsLength end end

This can be sped up a bit using some branch-and-bound by skipping i/j sequences which are shorter than the current maxSubsLength, but asymptotically this is still O(n^2). Slow, but with a big plus on its side: correct!

这篇关于发现有相同数量的1和0的最大子二进制套的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！