Longest Valid Parentheses

given a string containing just the

characters <code>‘(‘</code> and <code>‘)‘</code>, find the length

of the longest valid (well-formed) parentheses substring.

for <code>"(()"</code>, the longest valid parentheses substring

is <code>"()"</code>, which has length = 2.

another example is <code>")()())"</code>, where the longest valid

parentheses substring is <code>"()()"</code>, which has length = 4.

也就是说要找到最长的子串满足匹配规则。

算法思路，建立两个数组pre[]和post[],生成规则如下：

pre数组：从前向后遍历原字符串s，若该下标i所对应的字符为‘(‘，则

：(1)若i为0，pre[i]=1;(2)若pre[i-1]&lt;0,pre[i]=1(3)其余情况，pre[i]=pre[i-1]+1;

post数组：从后向前遍历原字符串s，若该下标i所对应的字符为‘)‘，则：(1)若i为s.length-1，post[i]=1;(2)若post[i+1]&lt;0,pre[i]=1(3)其余情况，pre[i]=pre[i+1]+1;

例如：字符串")()())"的pre数组为 -1  1  0  1  0  -1，post数组为2

 1  2  1  2  1

然后在pre数组中从后向前找到第一个值为0的下标，若没有，则从pre数组中找出的最长子串为0，若找到，再向前找出第一个小于0的下标，或者全部大于0，此时下标递减到0，则从pre数组中找出的最长子串的长度就是这两个下标的差值。

同理，在post数组中从前向后找第一个值为0的下标，然后再找第一个值小于0的下标或者下标到s.length-1，从post数组中找到的子串长度即这两个下标的差值。

因此，满足条件的最长子串的长度就是从pre数组和post数组中找到的长度的最大值。

因为算法中遍历了两次原字符串，一次pre数组和一次post数组，因此时间复杂度为o(n)，空间复杂度为两个数组pre和post，为o(n)

////////////////////////////////////////////////////////////////////////////////////////////分割线/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

看了一下网上的做法，转载一下：

转自

这道题可以用一维动态规划逆向求解。假设输入括号表达式为string s，维护一个长度为s.length的一维数组dp[]，数组元素初始化为0。

dp[i]表示从s[i]到s[s.length -

1]包含s[i]的最长的有效匹配括号子串长度。则存在如下关系：

dp[s.length - 1] = 0;

i从n - 2 -&gt; 0逆向求dp[]，并记录其最大值。若s[i] == ‘(‘，则在s中从i开始到s.length -

1计算dp[i]的值。这个计算分为两步，通过dp[i + 1]进行的（注意dp[i + 1]已经在上一步求解）：

在s中寻找从i + 1开始的有效括号匹配子串长度，即dp[i + 1]，跳过这段有效的括号子串，查看下一个字符，其下标为j = i

+ 1 + dp[i + 1]。若j没有越界，并且s[j] == ‘)’，则s[i ... j]为有效括号匹配，dp[i] =dp[i + 1] +

2。

在求得了s[i ... j]的有效匹配长度之后，若j + 1没有越界，则dp[i]的值还要加上从j +

1开始的最长有效匹配，即dp[j + 1]。