最长合法括号字串

题目

题目连接

一个合法的括号字符串满足以下条件：

• 1.字符串“()”被认为是合法的。
• 2.如果字符串 “X” 与 “Y” 是合法的，则 “XY” 也被认为是合法的。
• 3.如果字符串 “X” 是合法的，则 “(X)” 也是合法的。

例如，“()”，“()()”，“(())” 这些都是合法的。

现在，给定一个由 ( 和 ) 组成的字符串 S。

请你求出其中的最长合法括号子串的长度以及数量。

输入格式

共一行，一个由 ( 和 ) 组成的字符串。

输出格式

一行两个整数，表示最长合法括号子串的长度以及数量。

如果不存在合法括号子串，则输出 0 1。

数据范围

前六个测试点满足： 1 ≤ ∣ S ∣ ≤ 100 1≤|S|≤100 1≤∣S∣≤100。

所有测试点满足： 1 ≤ ∣ S ∣ ≤ 1 0 6 1≤|S|≤10^6 1≤∣S∣≤106。

输入样例1：

)((())))(()())

输出样例1：

6 2

输入样例2：

))(

输出样例2：

0 1

代码

#include <iostream>
#include <stack>
using namespace std;

int dp[1001000]={0};
int main(){
    int maxl=0,ans=1;
    string str;
    stack<int>s;
    cin>>str;
    for(int i=0;i<str.size();i++){
        if(str[i]=='('){
            s.push(i);
        }
        else{
            if(!s.empty()){
                int top=s.top();
                s.pop();
                dp[i]=dp[top-1]+i-top+1;
                if(dp[i]>maxl){
                    maxl=dp[i];
                    ans=1;
                }
                else if(dp[i]==maxl){
                    ans++;
                }
            }
        }
    }
    cout<<maxl<<" "<<ans<<endl;
    return 0;
}