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.

class Solution {
public:
    int longestValidParentheses(string s) {
        /*
        //using stack
        int res = 0, start = 0, n = s.size();
        stack<int> st;
        for(int i = 0; i<n; i++){
            if(s[i] == ')'){
                if(!st.empty()){
                    st.pop();
                    res = st.empty() ? max(res, i - start + 1) : max(res, i - st.top());
                }
                else start = i + 1;
            }
            else st.push(i);
        }
        return res;
        */
        //using dp
        int n = s.size(), maxans = 0;
        int *dp = new int[n];
        for(int i = 0; i<n; i++)
            dp[i] = 0;
        for(int i = 1; i<n; i++){
            if(s[i] == ')'){
                if(s[i-1] == '(')
                    dp[i] = (i-2 >= 0 ? dp[i-2] : 0) + 2;
                else{
                    if(i - 1 - dp[i-1] >= 0 && s[i - 1 - dp[i-1]] == '(')
                        dp[i] = (i-2-dp[i-1] >= 0 ? dp[i-2-dp[i-1]] : 0) + dp[i-1] + 2;
                }
                maxans = max(maxans, dp[i]);
            }
        }
        return maxans;
    }
};

注意new之后的数组未必初始化为0.
另外还有一种O(1)空间的解法。所有解析见下面的链接。
https://leetcode.com/problems/longest-valid-parentheses/solution/