[leetcode/lintcode 题解] 阿里算法面试真题：最长有效括号

描述
有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为k。给出一个只包含'(' 和')'的字符串，找出其中最长的左右括号正确匹配的合法子串。

在线评测地址：领扣题库官网

样例1
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

样例2
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

考点

• dp

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

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

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] == ')' && 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;
    }
};

更多题解参考：九章官网solution