题目

求最长的有效括号的长度。题目对有效括号的定义没有说清楚，我以为是连续若干个()，实际上有效括号P的定义如下:

() is P
PP is P
(P) is P

求解

这道题分类在动态规划下面，我尝试做了一下没有做出来。然后看到讨论区的动态规划解法，觉得有点难想到。但是另一个使用栈的解法比较有意思。

使用栈解决

依次把括号的index入栈，如果遇到'('就push,如果遇到')'且栈顶是'('就pop，这样到最后，能匹配上的括号全部都出栈了，
在栈里剩下的括号是没有匹配到的。这里仔细看一下栈里面剩下的括号，可以发现有一个特点，它们是字符串里所有的连续有效括号的分隔点，
每两个分割点之间一定是有效括号，我们遍历栈里剩下的元素，求出所有的有效括号的长度即可。

  str: )(()(())))()()   len:14
stack: ↑        ↑
分隔点: 0        9

int longestValidParentheses(string s) {
    stack<int> stack;
    int len = s.length();
    for (int i = 0; i < len; i ++) {
        if (s[i] == '(') {
            stack.push(i);
            continue;
        }
        if (!stack.empty() && s[stack.top()] == '(') {
            stack.pop();
        } else {
            stack.push(i);
        }
    }
    if (stack.empty()) return len;
    else {
        int maxNum = -1;
        int end = len;
        while(!stack.empty()) {
            int start = stack.top();
            stack.pop();
            maxNum = max(maxNum, end - start - 1);
            end = start;
        }
        maxNum = max(maxNum, end);// 这里容易漏掉，最后还要比较一次
        return maxNum;
    }
}

使用动态规划

思路来源自讨论区，不是很好想。

定义dp[i]是以第i个元素结尾的最长有效括号。

        ┏-0                             if str[i] == '('
dp[i] = ┠-dp[i-2] + 2                   if str[i] == ')' && str[i-1] == '('
        ┗-dp[i-1] + 2 + dp[i-dp[i-1]-2] if str[i] == ')' && str[i-1] == ')'

代码