LeetCode 32. 最长有效括号 （DP|栈）

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 

"()()" 两种思路：

/*

第一种
思路:利用栈记录括号的下标(数组中的位置).
	1.当匹配完左右括号时，栈为空，说明在迟之前的都是有效配对
	2. 当匹配完左右括号时，栈非空，说明当前元素位置到栈顶元素之间的都是有效配对
	3.看代码，好理解 e.g    1.()()   
						    2.)()() 
*/

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> ss;
        int ans=0;
        for(int i=0;i<s.size();i++){
            if(s[i]==')' && !ss.empty() && s[ss.top()]=='('){
                ss.pop();
                if(ss.empty()){
                    ans=i+1;
                }else if(i-ss.top()>ans){
                    ans=i-ss.top();
                }
            }else ss.push(i);
        }
        return ans;
    }
};

/*
第二种 
思路: dp[i]:记录以s[i-1]为结尾的最长有效配对
	  两种情况：
	  		当前为s[i] 
			1.以'(' 结尾的最长有效长度为0
			2.以')' 结尾的长度,当前面存在匹配的'(',才计算 
				1)当以s[i-1]结尾的最长匹配数大于0时，说明dp[i+1]=dp[i]+dp[i-dp[i]-1]+2;
				2)当以s[i-1]结尾的最长匹配数等于0时,说明dp[i+1]=dp[i-1]+dp[i]+2; 
		eg.
			1).
			s[i-dp[i]-1]:当模拟到s[5]时, s[i-dp[i]-1]就是s[2]. 
				()(())
		   位置:012345
		     DP:020026
		     
		     
		    2).
		    	()()()
		   位置:012345
		     DP:020406
		     
	hint:需要初始化一下DP数组 
*/
int longestValidParentheses(string s) {
    int dp[101001];
    for(int i=0;i<101001;i++) dp[i]=0;
    int ans=0;
    for(int i=0;i<s.length();i++){
        if(s[i]=='(') dp[i+1]=0;
        else if(s[i-dp[i]-1]=='('){
            if(dp[i]>0) dp[i+1]=dp[i]+dp[i-dp[i]-1]+2;
            else dp[i+1]=dp[i-1]+dp[i]+2;
        }
        ans=max(ans,dp[i+1]);
    }
    return ans;
}