【题解】括号字符串的最长有效长度

动态规划解法，dp[i]表示以i为开始的最长有效括号字符串的长度，
只有以'('开始有可能出现有效括号串，对于每一个'('来说，要凑出一个有效的括号字符串 肯定是'('+一段有效的括号字符串+')' +一段有效的括号字符串

#include<iostream>

using namespace std;

const int MAXN = 1e5+10;
int main()
{
    string s;
    cin >> s;
    int ans = 0;
    int dp[MAXN]={0};
    for(int i = s.length()-2 ; i >= 0 ; i--)
    {
        if(s[i]=='(')
        {
            int next = i+dp[i+1]+1;//去掉左括号+一段有效的括号字符串之后的位置
            if(next <s.length() && s[next]==')')//+')'
            {
                dp[i] = dp[i+1]+2;
                if(next+1 <s.length()){dp[i]+=dp[next+1];}//加后面的一段有效的括号字符串
            }
        }
        ans = max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}

栈解法：顺序遍历字符串，对于每一个字符来说，如果是'('就入栈，如果是')'并且栈顶是'(',那就出栈，并且记一下当前的长度。

#include<iostream>
#include<stack>
using namespace std;
struct node{
    char c;
    int index;
};
const int MAXN= 1e5+10;
int main()
{
    string s;
    cin >> s;
    stack<node> S;
    int ans = 0;
    for(int i = 0 ;i < s.length();i++)
    {
        if(s[i]==')'&&!S.empty()&&S.top().c=='(')
        {
                S.pop();
                int b = 0;
                if(!S.empty()){ans = max(ans,i-S.top().index);}
                else{ans = i+1;}
        }
        else{S.push(node{s[i],i});}
    }
    cout<<ans<<endl;
    return 0;
}