leetcode2272 最大波动的子字符串

思路：

枚举+动态规划。

实现：

 1 class Solution{
 2 public:
 3     int largestVariance(string s){
 4         int n=s.length();
 5         int res=0;
 6         for(int i=0;i<26;i++){
 7             char x=char('a'+i);
 8             for(int j=0;j<26;j++){
 9                 char y=char('a'+j);
10                 if(j==i){
11                     continue;
12                 }
13                 vector<int>t(n);
14                 for(int k=0;k){
15                     if(s[k]==x){
16                         t[k]=1;
17                     }
18                     else if(s[k]==y){
19                         t[k]=-1;
20                     }
21                     else{
22                         t[k]=0;
23                     }
24                 }
25                 vector<int>f(n+1,0);
26                 for(int k=0;k){
27                     f[k+1]=f[k]+t[k];
28                 }
29                 int last=-1,minn=0x3f3f3f3f;
30                 for(int k=0;k){
31                     if(t[k]==-1){
32                         for(int p=last+1;p<=k;p++){
33                             minn=min(minn,f[p]);
34                         }
35                         last=k;
36                     }
37                     res=max(res,f[k+1]-minn);
38                 }
39             }
40         }
41         return res;
42     }
43 };