动态规划

取以下三种情况中 $\texttt{NOI}$ 子序列的最大值：

• 在字符串开头插入一个 $\texttt{N}$。
• 在字符串结尾插入一个 $\texttt{I}$。
• 在字符串中间某个位置插入一个 $\texttt{O}$。

对于前两种情况，计算原字符串中 $\texttt{NOI}$ 子序列的数量，分别加上原字符串中 $\texttt{OI}$ 子序列的数量和 $\texttt{NO}$ 子序列的数量即可。

对于第三种情况，动态维护一个位置前 $\texttt N$ 的数量和一个位置后 $\texttt I$ 的数量即可快速计算。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
long long ans,cnt,res,now,sum,pre,suf;
char s[100'005];
int n;
int main(){
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++){
        if(s[i]=='N') ++sum;
        if(s[i]=='O') cnt+=sum;
        if(s[i]=='I') now+=cnt;
    }
    res=now;
    ans=max(ans,res+cnt);
    sum=0,cnt=0,now=0;
    for(int i=n;i>=1;i--){
        if(s[i]=='I') ++sum;
        if(s[i]=='O') cnt+=sum;
        if(s[i]=='N') now+=cnt;
    }
    ans=max(ans,res+cnt);
    sum=0,cnt=0,now=0;
    suf=count(s+1,s+n+1,'I');
    for(int i=1;i<=n;i++){
        cnt=max(cnt,pre*suf);
        if(s[i]=='N') ++pre;
        if(s[i]=='I') --suf;
    }
    ans=max(ans,res+cnt);
    printf("%lld\n",ans);
    return 0;
}