1、题目形容
给定一个长度为 N的数列，求数值严格枯燥递增的子序列的长度最长是多少。输出格局第一行蕴含整数 N。第二行蕴含 N 个整数，示意残缺序列。输入格局输入一个整数，示意最大长度。
数据范畴
1≤N≤10001
−1e9≤数列中的数≤1e9。
输出样例
73 1 2 1 8 5 6
输入样例
4
2、思路分析
这是一道经典dp问题，咱们要求的是最长回升子序列的长度，这个最长的子序列可能是以a[i]结尾的（咱们假如数字被存储在数组a中），咱们应用一个数组dp[i]来示意以a[i]为结尾的子序列的最大长度，咱们最终所求的就是dp数组中的最大值。
如果咱们需要求dp[i]，就是以a[i]为结尾的最大值，那么咱们就须要晓得它的前一个地位是谁，假如它的前一个数字是a[j]，那么dp[i] = dp[j] + 1，也就是以它前一个数字结尾的最大子序列长度再+1。j到底是谁咱们不分明，j的范畴是[1, i-1]，咱们把最大的（dp[j] + 1）找到，就是最大的dp[i]。
3、代码
#include<iostream>using namespace std;const int N = 1e3+10;int a[N],dp[N];int main(){ int n; cin>>n; int M = 0; for(int i=1;i<=n;++i)cin>>a[i]; for(int i = 1;i<=n;++i)//求dp[i]汇合 { dp[i] = 1;//dp[i]起码也有本身的长度 for(int j=1;j<i;++j)//看看以a[i]结尾的最长子序列的前一个数是哪一个 { if(a[j]<a[i]) { dp[i] = max(dp[i], dp[j]+1); } } //找最长子序列 M = dp[1]; for(int i=2;i<=n;++i) { M = max(M, dp[i]); } } cout<<M<<endl; return 0;}