以 ( 结尾的子字符串不考虑，因为不可能构成合法括号

    if s[i] == ‘)’

    1. s[i - 1] == ‘(‘，也就是字符串形如 “……()”，我们可以推出：

    dp[i] = dp[i − 2] + 2。
    因为结束部分的 “()” 是一个有效子字符串，并且将之前有效子字符串的长度增加了 2.

    1. s[i - 1] == ‘)’，也就是字符串形如 “…….))”，我们可以推出：

    if s[i - dp[i - 1] - 1] == ‘(‘，dp[i] = dp[i − 1] + dp[i − dp[i − 1] − 2] + 2。
    因为如果倒数第二个 )是一个有效子字符串的一部分（记为subs），我们此时需要判断 subs 前面一个符号是不是 ( ，如果恰好是(，我们就用 subs 的长度(dp[i - 1)加上 2 去更新 dp[i]。除此以外，我们也会把子字符串 subs 前面的有效字符串的长度加上，也就是 dp[i − dp[i − 1] − 2].
    边界情况

    1. i - 2 有可能小于零越界了，这种情况下就是只有 () ，前面记为 0 就好了.
    2. i - dp[i - 1] - 1 和 i - dp[i - 1] - 2 都可能越界，越界了当成 0 来计算就可以了.
    1. int longestValidParentheses(string s) {
    2.     int maxLen = 0;
    3.     vector<int> dp(s.length());
    4.     for (int i = 1; i < s.length(); i++) {
    5.         if (s[i] == ')') {
    6.             if (s[i - 1] == '(') {
    7.                 dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
    8.             } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
    9.                 dp[i] = (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
    10.             }
    11.         }
    12.         maxLen = max(dp[i], maxLen);
    13.     }
    14.     return maxLen;
    15. }

    时间：O(N)
    空间：O(N)