krl*_*mlr 2 language-agnostic algorithm
如何在二进制字符串中找到最长的子字符串,其中余额(即1和0的数量之差)> = 0？
例:
01110000010 - > 6:011100
1110000011110000111 - > 19:整个字符串
虽然这个问题看起来非常类似于最大值连续子序列(最大连续和)问题,但动态编程解决方案似乎并不明显.在分而治之的方法中,如何进行合并？毕竟是一种"高效"的算法吗？(一个简单的O(n ^ 2)算法将迭代所有可能起点的所有子串.)
这是查找子字符串的修改变体,带有一些附加条件.不同之处在于,在链接问题中,只允许这样的子串,其中余额永远不会低于零(在向前或向后方向上查看字符串).在给定的问题中,如果平衡在稍后阶段恢复,则允许平衡降至零以下.
我有一个需要O(n)额外内存和O(n)时间的解决方案.
我们将索引的"高度"表示h(i)为
h(i) = <number of 1s in the substring 1..i> - <number of 0s in the same substring>
现在可以将问题重新表述为:发现i和j诸如h(i) <= h(j)和j-i -> max.
显然,h(0) = 0如果h(n) = 0,那么解决方案就是整个字符串.
现在让我们计算数组,B以便B[x] = min{i: h(i) = -x}.换句话说,让B[x]是最左边的索引i处h(i)= -x.
该数组B[x]的长度最多n,并在一个线性通道中计算.
现在我们可以迭代原始字符串,并为每个索引i计算最长序列的长度,其中非负余额结束i如下:
Lmax(i) = i - B[MIN{0, h(i)}]
Lmax(i)所有最大的i将给你所需的长度.
我把证明留作练习:)如果你想不通,请联系我.
此外,我的算法需要2次传递原始字符串,但您可以将它们合并为一个.
| 归档时间： |
|
| 查看次数： |
1502 次 |
| 最近记录： |