Longest Valid Parentheses

 //first solution
DP. The main idea is as follows: I construct a array longest[], for any longest[i], it stores the longest length of valid parentheses which is end at i.
And the DP idea is :
If s[i] is '(', set longest[i] to 0,because any string end with '(' cannot be a valid one.
Else if s[i] is ')'
     If s[i-1] is '(', longest[i] = longest[i-2] + 2
     Else if s[i-1] is ')' and s[i-longest[i-1]-1] == '(', longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]

   int longestValidParentheses(string s) {
            if(s.length() <= 1) return 0;
            int curMax = 0;
            vector<int> longest(s.size(),0);
            for(int i=1; i < s.length(); i++){
                if(s[i] == ')'){
                    if(s[i-1] == '('){
                        longest[i] = (i-2) >= 0 ? (longest[i-2] + 2) : 2;
                        curMax = max(longest[i],curMax);
                    }
                    else{ // if s[i-1] == ')', combine the previous length.
                        if(i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '('){
                            longest[i] = longest[i-1] + 2 + ((i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0);
                            curMax = max(longest[i],curMax);
                        }
                    }
                }
                //else if s[i] == '(', skip it, because longest[i] must be 0
            }
            return curMax;
    }

 //a more concise version

    int longestValidParentheses(string s) {
        int max = 0;
        vector<int> dp(s.size()+1,0);
        for(int i = 1; i < s.size(); i++) {
            if(s[i] != ')' or s[i-dp[i]-1] != '(') continue;
            dp[i+1] = 2 + dp[i] + dp[i-dp[i]-1];
            if(dp[i+1] > max) max = dp[i+1];}
        return max;
    }

//method 2: use a stack. The top of the stack stores the newest position of '(' to

//be matched, or the newest position of ')' that is not matched. 

    int longestValidParentheses(string s) {
        int len=s.length();
        stack<int> stak;int maxn=0;
        for(int i=0;i<len;i++){
            if(s[i]=='(')
                stak.push(i);
            else if(s[i]==')'){
                if(!stak.empty()&&s[stak.top()]=='('){
                    stak.pop();
                    maxn=max(maxn,stak.empty()?i+1:i-stak.top());
                }    
                else{
                    stak.push(i);
                }    
            }    
        }
        
        return maxn;
    } 

//method 3, by anniekim

 // Traverse the string twice, taking O(n) time.
// First time, mark all the matching parentheses as 'k' (push the index of '(' into <stack>).
// Second time, count the longest consecutive 'k'.

    int longestValidParentheses(string s) {
        stack<int> left;//position of '('
        for(int ii = 0; ii < s.size(); ++ii){
            if (s[ii] == '(') left.push(ii);
            else if (!left.empty()){//')'
                s[ii] = 'k';
                s[left.top()] = 'k';
                left.pop();
            }
        }
        int maxLength = 0;
        int length = 0;
        for(int ii = 0; ii < s.size(); ++ii){
            if (s[ii]=='k'){
                ++length;                
                if (maxLength < length) maxLength = length;
            }
            else length = 0;

        }
        return maxLength;
    }