我正试图解决我之前问过的aproblem的变体：
给定一个括号字符串（长度范围查询，查找平衡的最长子序列
每个查询
我发现这个问题很相似，但只有一个o（n^3）算法。
我认为dp[i, j] = longest balanced subsequence in [i .. j]格式的dp解决方案应该可以工作，因为一旦计算出来，就可以通过查询dp表来回答所有范围查询。但是，由于可能的输入字符串长度过大，即使对此问题的o（n^2）解决方案也会超过时间限制。
此外，使用堆栈跟踪匹配括号的技巧不再直接起作用，因为您要查找的是子序列，而不是子字符串。
我有一个方法，我认为可能有用，但不确定：
区间内平衡圆括号的最长子序列的长度是该区间内平衡圆括号的最长不重叠子序列的长度之和。
例如，如果有字符串0 1 2 3 4 5 6 7 8 9 10 11 12 13 14) ) ( ( ) ( ( ) ) ) ) ( ( ) )
区间[0，8]中平衡圆括号的最长子序列的长度为5此长度等于间隔内最长的不重叠子字符串的长度之和：“（”+“（）”。
这种方法总是有效的，还是有更好的方法？
最佳答案
由于其他人发布了答案，这里有一个O(n)对O(1)空格的单个查询的答案。保持paren的计数平衡，并指向最后一个打开和最后一个关闭的paren。在结束字符串之前，向前扫描最后一个打开的部分以找到另一个打开的paren。然后从最后一个打开和最后一个关闭paren的最大值向前扫描，以找到下一个关闭paren。如果这样找到一对，则增加平衡的parens数当您到达字符串的末尾时，您将拥有正确的计数，即使您错误地将paren配对。
实际上可能有平衡子空间的多个最大子序列。但是，如果你采取平衡子的最大子序列，用最左边的可能打开的PARN替换每一个打开的PARN，然后用最左边的可能的打开的父子替换每个紧邻的PARN，结果将是你找到的那些。（作为指导性练习留给读者的证据。）
这是伪代码。
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)预计算和O(n)空间，并且每个范围查询都需要O(log(n))时间。这是这个问题的提示假设我们有两个街区A和B紧挨着。每一个内部都有一些paren的平衡子序列，右边有一些额外的开放paren，左边有一些额外的封闭paren然后组合块C具有以下内容：
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)
我留给你一个练习，就是找出要预计算的块集合，以便能够在时间
O(log(n))内计算任何块。