2021/4/11，题意如下：

困难题瞄了题解才有思路，第一种思路是用栈，栈中存的是左括号的下标，每次输入一个右括号就让这个右括号的下标减去和没有构成匹配前一个左括号的下标。需要注意的是要在输入之前在栈中加入一个-1让第一个匹配的右括号有值。
c++参考代码：

class Solution {
public:
    int longestValidParentheses(string s) {
     stack<int> st;
     int n=s.size();
     int ans=0;
     st.push(-1);
     for(int i=0;i<n;i++)
     {
         if(s[i]==')')
         {
             st.pop();
            if(st.empty())
            st.push(i);
            else
            {
               ans=max(ans,i-st.top());
            }
         }
         else
         {
           st.push(i);
         }
     }
     return ans;
    }
};

时间复杂度：O(N)，空间复杂度O(N)。

第二种思路是动态规划，dp[i]表示当前括号能构成的最长匹配长度，显然左括号都不能匹配，左括号的dp值都为，当输入一个右括号时有两种情况，当它前面是左括号时它的dp值就是左括号的值加二，当前面是右括号时，我们要看和这个右括号匹配的左括号前是不是左括号，如果是的话为前一个右括号的dp值+2并且还要加上前面那个匹配上的右括号前一个括号的dp值（因为连起来了），看着可能有点绕，看代码好理解一点。

class Solution {
public:
    int longestValidParentheses(string s) {
        int n=s.size();
        int ans=0;
     vector<int> dp(n,0);
     for(int i=1;i<n;i++)
     {
         if(s[i]==')')
         {
             if(s[i-1]=='(')
             {
                  dp[i]=(i>=2? dp[i-2]:0)+2;
             }
             else if(i-dp[i-1]>0&&s[i-dp[i-1]-1]=='(')//i-dp[i-1]是前一个括号的匹配长度
             {
                     dp[i]=dp[i-1]+((i-dp[i-1]-2)>=0? dp[i-dp[i-1]-2]:0)+2;
             }
             ans=max(ans,dp[i]);
         }
     }
     return ans;
    }
};

时间复杂度：O(N)，空间复杂度O(N)。
参考资料
·力扣官方题解