题目链接
思路
关键在于想到括号匹配用栈维护的一个过程。
求最长的子串,所以每一个右括号尽可能匹配能匹配的最近的左括号。
\(dp[i]\):第i位向左匹配能匹配到的最长距离。
若当前位置\(s[i]=)\)且\(stack.size()>0\),那么就说明当前位置的右括号可以匹配到左括号,到这一位的最长距离即是\(dp[i]=i-stack.top()+1+dp[stack.top()-1]\)。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
char s[N];
int dp[N];
stack<int> stk;
void solve() {
scanf("%s", s + 1);
int len = strlen(s + 1);
int mx = 0, cnt = 1;
for(int i = 1; i <= len; i++) {
if(s[i] == '(') stk.push(i);
else {
if(stk.size() > 0) {
dp[i] = i - stk.top() + 1 + dp[stk.top() - 1];
stk.pop();
if(mx < dp[i]) mx = dp[i], cnt = 1;
else if(mx == dp[i]) cnt++;
}
}
}
printf("%d %d\n", mx, cnt);
}
int main() {
// freopen("in.txt", "r", stdin);
// int t; cin >> t; while(t--)
solve();
return 0;
}