题解 | #括号字符串的最长有效长度#

//经典动态规划
//申请一个同样长度的dp表
//dp[i]的含义为以i为结尾的最长有效长度是多少
#include<bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    int len=-1;
    int *dp=new int[str.size()-1];
    dp[0]=0;
    for(int i=1;i<str.size();i++){
        if(str[i]=='('){//以（结尾的长度必定为0
            dp[i]=0;
        }
        else{//如果dp[i]=')'
            if(str[i-1]=='('){//此时正好能凑出来一对括号
                dp[i]+=2;
                dp[i]+=i-2>=0?dp[i-2]:0;
                len=len>dp[i]?len:dp[i];
            }
            else{//此时说明str[i-1]==')'
                if(i-dp[i-1]-1>=0){
                    if(str[i-dp[i-1]-1]=='('){
                        dp[i]=dp[i]+2+dp[i-1];
                        dp[i]+=i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0;
                        len=dp[i]>len?dp[i]:len;
                    }
                }
            }
        }
    }
    cout<<len<<endl;
    return 0;
}