问题（DP）

代码

方案1：O(n²)
dp[i] := 以a[i] 为结尾的最长上升子序列的长度

由于以a[i]为结尾的子序列只有两种情况：
（1） 只包含a[i]的序列
（2）满足 j < i 并且 a[j] < a[i] 的以a[j] 为结尾的上升子列末尾加上a[i]之后得到的子序列

所以，递推关系如下：
dp[i] = max{1 , dp[j] + 1 | j < i 且 a[j] < a[i] }

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int MAX_N = 1000; 
int dp[MAX_N+1]; // DP数组 //输入 
int n = 5;   
int a[5] = {4, 2, 3, 1, 5};void solve(){int res = 0;for(int i = 0 ; i < n ; i ++){dp[i] = 1;for(int j = 0 ; j < i ; j ++){if(a[j] < a[i]){dp[i] = max(dp[i], dp[j]+1);}}res = max(res, dp[i]);}printf("%d\n", res);
} int main(){	solve(); return 0;
}

方案2：O(nlogn)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int MAX_N = 1000; 
const int INF = 100000;
int dp[MAX_N+1]; // DP数组 //输入 
int n = 5;   
int a[5] = {4, 2, 3, 1, 5};void solve(){fill(dp, dp+n, INF);for(int i = 0 ; i < n ; i ++)*lower_bound(dp, dp+n, a[i]) = a[i];printf("%d\n",lower_bound(dp, dp+n, INF) - dp);
} 	int main(){	solve(); return 0;
}