n^2 做法 dp[i]表示以i结尾最大的长度

状态转移方程 dp[i]=max(dp[i],dp[j]+1); j<i;

#include <stdio.h>
#include <algorithm>

using namespace std;
const int maxn=1010;
int h[maxn],dp[maxn];
int n,ma;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&h[i]);
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(h[i]>h[j])dp[i]=max(dp[i],dp[j]+1),ma=max(ma,dp[i]);
        }
    }
    printf("%d\n",ma+1);
    return 0;
}

nlgn做法 dp[i]表示 长度为i的子序列末尾最小元素是什么

每读入一个数都可以更新dp[i],假如大于最末尾那个就直接添加 不然就找到可以加入的最末位置的后一位更新

#include <stdio.h>
#include <algorithm>

using namespace std;
const int maxn=1010;
int h[maxn],dp[maxn];
int n,cnt;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&h[i]);
    dp[cnt]=h[0];
    for(int i=1;i<n;i++){
        if(h[i]>dp[cnt])dp[++cnt]=h[i];
        else{
            int l=0,r=cnt;
            while(l<r){
                int mid=l+r>>1;
                if(dp[mid]>=h[i])r=mid;
                else l=mid+1;
            }
            dp[r]=h[i];
        }
    }
    printf("%d\n",cnt+1);
    return 0;
}