一. 题目

二. 思路

1. DP

2. 贪心

三. 代码

1. DP

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int N=1e3+10;

int n;
int a[N];

class DP
{
public:
    int f[N];

public:
    DP()
    {
        initIO();
        fill(f, f+N, 0);
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    int work()
    {
        int maxLen=1;
        for(int i=1;i<=n;++i)
        {
            f[i]=1;//每个数自己至少为1
            for(int j=1;j<i;++j)
                if(a[j]<a[i])
                    f[i]=max(f[i], f[j]+1);
            maxLen=max(f[i], maxLen);
        }
        
        return maxLen;
    }
}dp;

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    cout<<dp.work();
}