算法

(逆向dp) $O(n)$

一般对于最长XX问题容易想到利用 $\rm DP$ 求解，在这题中利用逆向 $\rm DP$，设状态$dp[i]$为从$i$到$len -1$中，以 $i$ 开头的最长合法子串长度：

• 初始化：$dp[len - 1] = 0$
• 如果 s[i] = ')'，则跳过，因为不可能有由')'开头的串
• 如果 s[i] = '('，则需要找到右括号和它匹配，可以跳过以$i + 1$开头的合法子串，则需要看$j = i + dp[i + 1] + 1$是否为右括号。如果没越界且为右括号，那么有$dp[i] = dp[i + 1] + 2$，此外在这个基础上还要将$j + 1$开头的子串加进来（只要不越界）

C++ 代码

class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.size() <= 1)   return 0;
        int res = 0;
        vector<int> dp(s.size(), 0);    //初始化
        for(int i = s.size() - 2; i >= 0; i--)
        {
            if(s[i] == '(') //如果s[i] = '('，则需要找到右括号和它匹配，可以跳过以i + 1开头的合法子串，则需要看j = i + dp[i + 1] + 1是否为右括号
            {
                int j = i + dp[i+1] + 1;
                if(s[j] == ')' and j < s.size())    //如果没越界且为右括号
                {
                    dp[i] = dp[i+1] + 2;
                    if(j + 1 < s.size())  //还要将j + 1开头的子串加进来
                        dp[i] += dp[j+1];
                }    
                res = max(res, dp[i]);
            }
        }
        return res;
    }
};