我试图解决的一个变种problem我刚才问：

I am trying to solve a variant of a problem I asked earlier:

给定的字符串的括号（长度＆其中; = 1,000,000）和列表   范围查询，找到平衡最长的子   内每个范围的括号为每个在＆lt; = 10万   查询

Given a string of parentheses (length <= 1,000,000) and a list of range queries, find the longest subsequence of balanced parentheses within each of the ranges for each of the <= 100,000 queries

我发现这个other SO质疑相似，但只有一个O（N ^ 3）算法。

I found this other SO question that is similar but only has an O(N^3) algorithm.

我认为，格式为： DP [I，J] =最长平衡子中的DP解决方案[我.. J] 应该工作，因为一旦计算，这将使刚刚通过查询DP表来回答所有的范围查询。然而，即使是O（N ^ 2）的解决这个问题会超出时限由于大可能的输入字符串的长度。

I believe that a DP solution of the form dp[i, j] = longest balanced subsequence in [i .. j] should work because once computed, this would enable to to answer all of the range queries just by querying the DP table. However, even an O(N^2) solution to this problem would exceed the time limits due to the large possible input string length.

此外，使用堆栈跟踪不再直接匹配括号的把戏工作，因为你正在寻找的子序列，而不是子。

Further, the trick of using a stack to keep track of matching parentheses no longer directly works because you are looking for subsequences, not substrings.

我有，我认为可能的工作，但我不知道的方式：

I have a method which I think might work but am not sure of:

均衡括号的间隔内最长的子序列的长度是平衡的括号的最长非重叠子串的长度的该时间间隔内的总和。

The length of the longest subsequence of balanced parentheses within an interval is the sum of the lengths of the longest non-overlapping substrings of balanced parentheses within that interval.

例如，如果您有字符串

0 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14

））（（）（（））））（（））

均衡括号的最长子序列中的间隔的长度[0,8]（含）是5。该长度等于该间隔内最长的非重叠子串的长度的总和的： （）+（（））。

The length of the longest subsequence of balanced parentheses in the interval [0, 8] (inclusive) is 5. This length is equal to that of the sum of the lengths of the longest non-overlapping substrings within the interval: "( )" + "( ( ) )".

请问这种方法始终持有，或是否有更好的办法？

Will this method always hold, or is there a better way?

推荐答案

由于其他人发布一个答案，这里是一个 O（N）答案跟单查询 O（1）的空间。保持括号平衡和指针的计数到最后开放和上次关闭的括号。直到你流掉的字符串，扫描着就上开另谋开括号。然后扫描从最近打开和上次关闭的括号的最大值来寻找下一个关闭括号。如果您发现一对的方式，增加括号平衡的计数。当你到达字符串的结尾，你就会有正确的计数，即使你配对的括号不正确。

Since someone else posted an answer, here is a O(n) answer to the single query with O(1) space. Keep the count of parens balanced and pointers to the last open and last closed paren. Until you've run off the string, scan forward on the last open to find another open paren. Then scan forward from the max of the last open and last closed paren to find the next closed paren. If you find a pair that way, increment the count of parens balanced. When you reach the end of the string, you will have the correct count, even though you paired up the parens incorrectly.

有可能实际上是平衡的括号多个最大序列。但是，如果你需要平衡括号中的任何最大序列，并与左，最有可能开括号，然后用左，最有可能开括号每一个接近括号更换每一个打开的括号，其结果将是你找到的人。 （证明留作启发读者的工作。）

There may actually be multiple maximal subsequences of balanced parens. But if you take any maximal subsequence of balanced parens, and replace every open paren with the left-most possible open paren, and then every close paren with the left-most possible open parens, the result will be the ones you found. (Proof left as an instructive exercise to the reader.)

下面是伪code。

parens = 0
last_open = 0
last_closed = 0
while last_open < len(str) && last_closed < len(str):
    if str[last_open] == ')':
        # We are looking for the next open paren.
       last_open += 1
    elif last_closed < last_open:
       # Start our search for a last closed after the current char
       last_closed = last_open + 1
    elif str[last_closed] == '(':
       # still looking for a close pair
       last_closed += 1
    else:
       # We found a matching pair.
       parens += 1
       last_open += 1
# and now parens has the correct answer.

和接下来我们有很多范围查询的挑战。事实证明，使这一快速采取 O（N） precomputation和 O（N）的空间，每个范围的查询将 O（日志（N））的时间。

And next we have the challenge of many range queries. It turns out that making this fast takes O(n) precomputation and O(n) space, and each range query will be O(log(n)) time.

下面是暗示了这个问题。假设我们有2块A和B紧挨着对方。其中每一个内部具有括号的均衡子序列的某些数目，额外开一定数目的括号可在右边，并且附加靠近一些数目的括号可用到左侧。然后组合块C有以下几点：

Here is the hint for that problem. Suppose that we have 2 blocks A and B right next to each other. Each of which internally has some number of balanced subsequence of parens, some number of additional open parens available to the right, and some number of additional close parens available to the left. Then the combined block C has the following:

C.balanced = A.balanced + B.balanced + min(A.open, B.close)
C.open = B.open + max(A.open - B.close, 0)
C.close = A.close + max(B.close - A.open, 0)

我离开你的锻炼搞清楚什么设置块precompute的是能计算出的任意的块时间 O（日志（N）） 。