/*** remain true to the original aspiration ***/
#include<bits/stdc++.h>

using namespace std;

//#pragma GCC optimize(2)
//#pragma G++ optimize(2)

#define pli pair < li , li >
#define ll long long
#define li long long
#define int long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1

#define Test           ll t;read(t); while(t--)
#define pb             push_back
#define all(x)         (x).begin(),(x).end()
#define fi             first
#define se             second
#define Faster         ios_base :: sync_with_stdio( 0 ); cin.tie( 0 ); cout.tie( 0 );
#define YES            printf("YES\n");
#define Yes            printf("Yes\n");
#define NO             printf("NO\n");
#define No             printf("No\n");

#define gcd(a, b)     __gcd( a , b )
#define lcm(a, b)     ( a * ( b / gcd( a , b ) ) )
#define popcount(x)    __builtin_popcount(x)
#define string(x)      to_string(x)
int dx[] = {-1, 0, 0, 1};//下左右上
int dy[] = {0, -1, 1, 0};
int dx1[] = {-1, -1, -1, 0, 1, 0, 1, 1, 0};//左下 中下 右下 左 中 右 左上 中上 右上
int dy1[] = {-1, 0, 1, -1, 1, 1, -1, 0, 0};
int dx2[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy2[] = {-1, 1, -2, 2, -2, 2, -1, 1};

const ll INF = 0x3f3f3f3f;
const ll mod = 998244353;
const double PI = 3.141592653589793238462643383279;

ll powmod(ll a, ll b) {
    ll res = 1;
    a %= mod;
    for (; b; b >>= 1) {
        if (b & 1)res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

ll square(ll x1, ll y1, ll x2, ll y2) { return abs(x2 - x1) * abs(y2 - y1); }

ll get_dist(ll x1, ll y1, ll x2, ll y2) { return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); }

ll get_jiao(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3, ll x4, ll y4) {
    int n1 = max(min(x1, x2), min(x3, x4)), m1 = max(min(y1, y2), min(y3, y4)), n2 = min(max(x1, x2),
                                                                                         max(x3, x4)), m2 = min(
            max(y1, y2), max(y3, y4));
    if (n2 > n1 && m2 > m1)return (n2 - n1) * (m2 - m1); else return 0;
}

template<typename T>
inline bool read(T &x) {
    x = 0;
    int f = 1;
    char c = getchar();
    bool ret = false;
    while (c < '0' || c > '9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c <= '9' && c >= '0') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
        ret = true;
    }
    x = x * f;
    return ret;
}

template<typename T, typename... Args>
inline bool read(T &a, Args &...args) { return read(a) && read(args...); }

template<typename T, typename Type>
inline void print(T x, const Type type) {
    if (x < 0)putchar('-'), x = -x;
    if (x > 9)print(x / 10, 0);
    putchar(x % 10 ^ 48);
    if (type == 1)putchar(' '); else if (type == 2)putchar('\n');
}

template<typename T, typename Type, typename... Args>
inline void print(T x, const Type type, Args... args) {
    print(x, type);
    print(args...);
}

///______________________ L E T ' S  B E G I N ______________________

int f[100001];
int a[100001];
signed main() {
    int n=0;
    int x;
    while(cin>>x)
        a[++n]=x;
    int ma1=-1;
    for(int i=1;i<=n;i++){
        int ma=0;
        for(int j=1;j<i;j++)
            if(a[j]>=a[i])ma=max(ma,f[j]);
        f[i]=ma+1;
//         print(1,1,f[i],1,ma1,2);
        ma1=max(ma1,f[i]);
    }
    memset(f,0,sizeof f);
    int ma2=-1;
    for(int i=n;i>=1;i--){
        int ma=0;
        for(int j=n;j>i;j--)
            if(a[j]>=a[i])ma=max(ma,f[j]);
        f[i]=ma+1;
        ma2=max(ma2,f[i]);
    }
    print(ma1,2,ma2,2);
}


///_______________________ G A M E  O V E R ! ______________________

这是一个ac代码;

可以看出,是O(n^2)的!

但是,在n=1e5的情况下,居然ac了???

还有:

测试数据错误!!!

in:

89 126 85 103 101 86 86 98 96 99 89 81 101 92 79 77 82 97 83 100 78 72 79 97 71 80 98 89 69 74

out:

12

6

与上述样例不对!!!ac代码错误!