Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

tag: dynamic programming

一开始我用了一些奇技淫巧，结果最坏情况是n^2，没有通过。

考虑动态规划。设置一个长度为s.size()的动态规划数组dp[]。

dp[i]表示从0-i里包括s[i]的合法字符串的最大长度；

对于i = i + 1, 如果s[i] == ‘(‘, dp[i] = 0;

如果s[i] == ‘)’, 检查最大匹配字符串之前的那个符号，即prev = i – dp[i-1] – 1;（如果prev<0;dp[i] = 0）

如果s[prev] == ‘)’，dp[i] = 0;

如果s[prev] == ‘(‘， dp[i] = dp[i-1] + 2 + dp[prev-1];(如果prev-1>=0的话)，这里我们是把两个合法字符串拼接起来。

class Solution {
public:
    int longestValidParentheses(string s) {
        int size = s.size();
        int dp[size];// dp[i] 表示从0到i的包括s[i]的最长字符匹配的长度
        int max = 0;
        dp[0] = 0;
        for(int i = 1; i < size; i++){
            if(s[i] == '('){
                dp[i] = 0;
            }
            else{
                int prev = i - dp[i - 1] - 1;
                if(prev >= 0 && s[prev] == '('){
                    dp[i] = dp[i - 1] + 2;
                    if(prev - 1 >= 0){
                        dp[i] += dp[prev - 1];
                    }
                }
                else{
                    dp[i] = 0;
                }
            }
            if(dp[i] > max){
                max = dp[i];
            }
        }
        return max;
    }
};