分组符号最大长度平衡子序列

Question

将B视为一组分组符号(,),[,],{和}.如果B的长度为0或者B具有以下形式之一,则称为平衡序列:{X} Y或[X] Y或{X} Y其中X和Y本身是平衡的.Balanced的示例:() - {[]()} [] - ...

现在的问题是找到一种有效的算法来找到给定输入的最大长度平衡子序列(不一定是连续的),该输入是这些分组符号的串.

例如,如果输入是(){([)] {(])}} [],则其中一个最大长度子序列是(){[] {()}} []

我几乎可以肯定解决方案是DP,但无论如何我解决它我发现我的算法不起作用的例子.我确信只有一种方法,即DP和Divide and Conquer的组合.但它并不高效,因为无论如何D&C部分将一遍又一遍地解决一些重叠的问题.

Answer 1

让我们做一些简单的观察:

1. 任何平衡的子序列都可以表示为A1 X A2 Y,where A1和A2是两个匹配的括号((),[]或{}),X并且Y是平衡的子序列(它们可以是空的).这是事实,因为在任何平衡的非空子序列中都有一个最左边的括号,它必须与某些东西相匹配.

2. X并且Y是独立的.如果不是这样,则子序列不平衡.

这些观察为我们提供了动态编程解决方案

我们假设f(L, R)是[L, R]子阵列中最长的平衡子序列.基数是一个空的子阵列.过渡如下:

f(L, R) = max(   
     f(L + 1, R) // ignore the first element    
     max(f(L + 1, K - 1) + 2 + f(K + 1, R)) for all K if brackets at positions L and K match
)

时间复杂度是O(N^3)因为存在O(N^2)子阵列并且O(N)每个子阵列都有过渡.可以使用标准答案重建技术重建最长的子序列本身.