！！！题解 | 最长的括号子串 学习这题 其实一个一维数组就够了 只选符合条件的进行处理 其他全=0

#include <algorithm>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestValidParentheses(string s) {
        // write code here
        //感觉想的不对 不知道括号匹配怎么判断 怎么转移状态
        /*
        其实只需要一个一维数组。不需要去记录i到j的子串有多少匹配字符 因为这没有意义，而且非常冗余，因为开头的下标没有意义，因为这个开头并不一定是正确的子串的开头
        所以设下标为i的子串的有效长度是dp【i】
    
         */
         int size=s.size();
         if(size<2)return 0;
         int res=0;
         vector<int> dp(size,0);
         for(int i=1;i<size;i++){//正常从0开始，但只有一个元素肯定是0，所以从1开始
            if(s[i]=='(')dp[i]=0;
            else{
                if(s[i-1]=='('){
                    if(i-2<0)dp[i]=2;
                    else dp[i]=dp[i-2]+2;
                }
                else{
                    if((i-dp[i-1]-1)>=0&&s[i-dp[i-1]-1]=='('){
                            dp[i]=i-dp[i-1]-2>=0?dp[i-1]+dp[i-dp[i-1]-2]+2:dp[i-1]+2;
                    }
                    else dp[i]=0;
                }
            }
            res=max(res, dp[i]);
        }
        return res; 
    }
};