将B视为一组分组符号(,),[,],{和}.如果B的长度为0或者B具有以下形式之一,则称为平衡序列:{X} Y或[X] Y或{X} Y其中X和Y本身是平衡的.Balanced的示例:() - {[]()} [] - ...
现在的问题是找到一种有效的算法来找到给定输入的最大长度平衡子序列(不一定是连续的),该输入是这些分组符号的串.
例如,如果输入是(){([)] {(])}} [],则其中一个最大长度子序列是(){[] {()}} []
我几乎可以肯定解决方案是DP,但无论如何我解决它我发现我的算法不起作用的例子.我确信只有一种方法,即DP和Divide and Conquer的组合.但它并不高效,因为无论如何D&C部分将一遍又一遍地解决一些重叠的问题.
algorithm optimization dynamic-programming divide-and-conquer
我正在尝试解决我之前问过的一个问题的变体：
给定一串括号（长度 <= 1,000,000）和范围查询列表，为 <= 100,000 查询中的每一个查询在每个范围内找到平衡括号的最长子序列
我发现了另一个类似的问题，但只有一个 O(N^3) 算法。
我相信这种形式的 DP 解决方案dp[i, j] = longest balanced subsequence in [i .. j]应该可以工作，因为一旦计算，这将能够仅通过查询 DP 表来回答所有范围查询。然而，由于可能的输入字符串长度很大，即使是这个问题的 O(N^2) 解决方案也会超过时间限制。
此外，使用堆栈跟踪匹配括号的技巧不再直接有效，因为您正在寻找子序列，而不是子字符串。
我有一种我认为可能有效但不确定的方法：
一个区间内平衡括号的最长子序列的长度是该区间内平衡括号的最长非重叠子串的长度之和。
例如，如果您有字符串
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
) ) ( ( ) ( ( ) ) ) ) ( ( ) )
区间[0, 8]（含）内平衡括号的最长子序列长度为5，该长度等于区间内最长非重叠子串的长度之和：“( )” + "( ( ) )"。
这种方法会一直有效，还是有更好的方法？