数据应该加强一下，我这错误代码都AC了

jielosc @ 2024-01-22 23:37:04

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int f[N], a[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    f[1] = a[1];
    int len = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (a[i] > f[len])
            f[++len] = a[i];
        else
        {
            *upper_bound(f + 1, f + 1 + len, a[i]) = a[i];
        }
    }
    cout << len << endl;
    return 0;
}

5
3 4 6 4 5

4

3

by lrb20120825 @ 2024-01-25 11:00:36

@jielosc 我的AC代码

#include<iostream>
using namespace std;    
const int maxn=12e5;
int n,ans,a[maxn],f[maxn];  
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];      
    }
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
        {

            if(a[j]<a[i])
            f[i]=max(f[i],f[j]+1);  
        }
    }
    for(int i=1;i<=n;i++)ans=max(ans,f[i]);
    cout<<ans;  
}

by Inferior_dust @ 2024-01-30 21:01:06

建议加强数据啊！！！

之前我在这一题用了同楼主的方法AC了这题，因为这原本是错的，所以我在做其他要找单调序列的题时都出错了（刚刚才发现原来我的代码是错的(QAQ

by ss12345678 @ 2024-01-31 23:24:00

@jielosc 这个贪心做法也是正解吧，LISnlogn的做法在别的题用过

by Inferior_dust @ 2024-02-01 11:47:01

@jielosc

*upper_bound(f + 1, f + 1 + len, a[i]) = a[i];

这里的len改为n就对了(有个苣告诉我的

by Mint_hibiscus @ 2024-02-01 11:47:41

@ss12345678

正确做法应该是

for(int i=1;i<=n;i++)
{
    int tp=lower_bound(f+1,f+n+1,a[i])-f;
    if(f[tp]==1e9) ans++;
    f[tp]=a[i];
}

二分的范围是1+n+1而不是1+len+1

by Mint_hibiscus @ 2024-02-01 11:48:20

@jielosc

by YRCTTT @ 2024-02-25 08:16:49

呵呵，题面却说“上升子序列”准确应该是“最长不下降子序列”。该改改题面喽。

by Special_Tony @ 2024-05-23 13:42:31

@realskc