【题解】最长下降子序列

题意

给你一个字符串，你可以在其中翻转一个区间，然后求该序列中最长的非降子序列的长度。

题解

由于这里只有和两个数，并且求的是子序列。先考虑和组成的非降子序列是什么形式的，有三种形式，即都是或先后或都是三种。那么在考虑存在翻转时怎么样翻转能够使得贡献最大。实际上这情况下，我们将中间的进行翻转能使答案的贡献最大，这个时候整体的长度和这种形式的长度是一致的。那么我们需要记录,,,四种情况下出现的最多值即可。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char str[N];
int main()
{
    scanf("%s",str);
    int n=strlen(str);
    int a=0,ab=0,aba=0,abab=0;
    for(int i=0; i<n; i++)
    {
        if(str[i]=='1')
            a++,aba++;
        else
            ab++,abab++;
        ab=max(ab,a);
        aba=max(aba,ab);
        abab=max(abab,aba);
    }
    printf("%d\n",abab);
    return 0;
}