最长上升子序列 贪心

• 贪心
  • 从前往后扫描每个数，对于每个数：
    • 如果现有的子序列的结尾都小于当前数，则创建新子序列，放到这个序列里
    • 如果现有的子序列的结尾有大于当前数的，将当前数放到结尾大于等于它的最小的子序列后面（贪心）

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1010;

int n=1;
int res;
int a[N];
int g[N];
int f[N];

int main()
{
    while(cin>>a[n]) n++;


    for(int i=n-1;i;i--)
    {
        f[i]=1;
        for(int j=n-1;j>i;j--)
        {
            if(a[i]>=a[j])
            f[i]=max(f[i],f[j]+1);
        }
        res=max(res,f[i]);
    }

    cout<<res<<endl;

    int cnt=0;

    for(int i=1;i<n;i++)
    {
        int k=0;

        while(k<cnt&&a[i]>g[k]) k++;

        g[k]=a[i];

        if(k>=cnt) cnt++;

    }

    cout<<cnt;

    return 0;

}