在二进制字符串中查找最长的正子串

Question

假设我有一个像100110001010001. 我想找到这样的子字符串：

• 尽可能长
• 总和 >0

所以最长的子串，有比 0s 多的 1s。

例如对于上面的字符串，100110001010001它将是：[10011]000[101]000[1]

实际上，找到这些的总长度是令人满意的，在这种情况下：9。

不幸的是，我不知道，怎么能不以蛮力的方式做到这一点。有什么想法吗？

Answer 1

正如现在发布的，您的问题似乎有点不清楚。“尽可能长”的有效子字符串的总长度可能意味着不同的事情：例如，在其他选项中，它可能是（1）每个索引左侧的最长有效扩展的列表（这将允许重叠）在列表中），（2）非重叠此类最长左扩展的最长组合，（3）非重叠有效子串的最长组合（其中每个子串不一定是最长的）。

\n\n

我将概述 (3) 的方法，因为它很容易转换为 (1) 或 (2)。从每个索引中查找最长的左扩展可以在O(n log n)时间和O(n)额外的空间中完成（对于O(n)时间上最长的有效子字符串，请参阅此处：查找最长的非负子数组）。O(n^2)通过这种预处理，可以通过动态编程在某种程度上优化的时间和额外的空间内找到有效的、不重叠的子串的最长组合O(n)。

\n\n

我们首先遍历字符串，存储代表部分总和的总和，直到（包括）s[i]，将零计数为-1。我们将每个部分和插入二叉树中，其中每个节点还存储值出现的索引数组，以及小于节点值的值的最左边索引。s[a]（如果到 的前缀s[b]总和大于 到 的前缀总和，则从b到 的子字符串的a1 多于零。）如果树中已有值，我们将索引添加到节点的索引数组中。

\n\n

由于我们从左到右遍历，只有当新的最低值插入到树中时，最左边的较低值索引才会更新 \xe2\x80\x94 并且仅针对具有以下值的节点进行更新之前的最低值。这是因为任何具有较低值的节点都不需要更新；如果树中已经存在任何具有较低值的节点，则任何具有较高值的​​节点都已经存储了最早插入的节点的索引。

\n\n

每个索引左侧最长的有效子串延伸到具有较低前缀和的最左侧索引，可以轻松地在树中查找。

\n\n

为了获得最长的组合，让f(i)代表最长的组合到索引i。然后等于可以添加f(i)索引的每个有效左扩展的最大长度。jf(j-1)

\n