题解 | #最长上升子序列(一)#

简单dp

#include<iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int *num = new int[n],*dp = new int[n];
    for(int i = 0;i < n;++i){
        cin >> num[i];
        dp[i] = 1;   //最少长度为自身1个
    }
    for(int i = 1;i < n;++i){
        for(int j = 0;j < i;++j){
            if(dp[j] + 1 > dp[i]){
                if(num[i] > num[j])
                    dp[i] = dp[j] + 1;
            }
        }
    }
    int len = 0;
    for(int i = 0;i < n;++i)
        len = max(len,dp[i]);
    cout << len;
}