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. http://leetcode.com/onli…

leetcode_longest_valid_parentheses.cpp

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        int ans = 0;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum = 0;
            if (ans >= n - i)
                break;
            for (int j = i; j < n; ++j) {
                if (s[j] == '(')
                    sum += 1;
                else 
                    sum -= 1;
                if (sum == 0)
                    ans = max(ans, j - i + 1);
                else if (sum < 0)
                    break;
            }
        }
        return ans;
    }
};

leetcode_longest_valid_parentheses_2.cpp

class Solution {
public:
    int longestValidParentheses(string s) {
        int ans = 0;
        int left = 0;
        stack<pair<int, int> > st;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') {
                st.push(make_pair(i, left));
                left = 0;
            }
            else if (!st.empty()) {
                left = i - st.top().first + 1 + st.top().second;
                ans = max(ans, left);
                st.pop();
            }
            else {
                left = 0;
            }
        }
        return ans;
    }
};