LeetCode——32. Longest Valid Parentheses(C++)

LeetCode——32. Longest Valid Parentheses(C++)
Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”.

Example 2:
Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.

Example 3:
Input: s = “”
Output: 0

Constraints:
0 <= s.length <= 3 * 104
s[i] is ‘(’, or ‘)’.

解题思路：
动态规划，dp[i]存储以i为终点时，此处往前有几个连续对子，
从0开始遍历，所有‘（’的对应的dp数组值为0，遇到‘）’则考察其往前可配对的情况，前一个为‘（’则其dp值为前前一个的dp值+2（相关边界情况见代码），前一个为‘）’则考察此‘）’的dp值，非零则进行进一步计算，为零则当前dp也为零；
代码：

class Solution {
public:
    int longestValidParentheses(string s) {
        int siz=s.size();
        vectordp;
        dp.resize(siz,0);
        int maxsiz=0;    //记录最大的配对数
        for(int i=0;i
            if(i&&s[i]==')')
            {
                if(s[i-1]=='(')
                {
                    if(i>2)dp[i]=2+dp[i-2];
                    else dp[i]=2;
                    if(maxsiz
                    if(i-1-dp[i-1]>=0&&s[i-1-dp[i-1]]=='(')
                    {
                        if(i-1-dp[i-1]==0)
                        dp[i]=dp[i-1]+2;
                        else
                          dp[i]=dp[i-1]+2+dp[i-1-dp[i-1]-1];  
                        if(maxsiz 
submission:
 
                
                
                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！