dp[i]表示以s[i]结尾的最长连续有效括号。
参考,官方解法里面的dp方法,官方解法写的很好可以看看,本题有一些细节边界问题挺适合dp练习的。
// if(s[i - dp[i - 1] - 1] match s[i])
// dp[i] = dp[i - dp[i - 1] - 2];
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, dp[N];
map<char, int > M;
bool is_match(char a, char b){
if(M[b] - M[a] == 1) return true;
return false;
}
int main(){
M['('] = 0; M[')'] = 1;
M['['] = 2; M[']'] = 3;
M['{'] = 4; M['}'] = 5;
string s;
cin >> s;
n = s.size();
dp[0] = 0;
for(int i = 1; i < n; i ++ ){
if(M[s[i]] % 2 == 0) dp[i] = 0;
else {
if(i - dp[i - 1] - 1 < 0) dp[i] = 0;
else {
if(is_match(s[i - dp[i - 1] - 1], s[i])){
dp[i] = i - dp[i - 1] - 2 >= 0 ? dp[i - 1] + dp[i - dp[i - 1] - 2] + 2 : dp[i - 1] + 2;
}
}
}
}
int res = 0;
for(int i = 0; i < n; i ++ ) res = max(res, dp[i]);
cout << res;
return 0;
}