Codeforces1307C - Cow and Message【思维】

题目：

给出一个字符串 $s$ ,要求求出其下标为等差数列的出现次数最多的子序列的出现次数。
$(1 \leq ∣ s ∣ \leq 1 0^{5})$

思路：

因为要求下标是等差数列，所以只需要考虑长度为 $1$ 或 $2$ 的子序列即可。
对于长度为1 的子序列，用一个一维计数即可。
对于长度为2的子序列，用一个二维数组计数。
复杂度： $O (26 * ∣ S ∣)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
char ss[N];
ll num1[26],num2[26][26];
int main()
{
    scanf("%s",ss+1);
    int len=strlen(ss+1);
    for(int i=1;i<=len;i++)
    {
        int t=ss[i]-'a';
        for(int j=0;j<26;j++)
            num2[j][t]+=num1[j];
        num1[t]++;
    }
    ll maxn=0;
    for(int i=0;i<26;i++)
        maxn=max(maxn,num1[i]);
    ll ans=maxn;
    maxn=0;
    for(int i=0;i<26;i++)
    {
        for(int j=0;j<26;j++)
            maxn=max(maxn,num2[i][j]);
    }
    ans=max(ans,maxn);
    printf("%lld\n",ans);
    return 0;
}