题目描述：给出一个数列{a1,a2,...,an},要求你选出尽量多的元素，使这些元素按其相对位置单调递增。
任务就是对于给定的序列，求出最长上升子序列的长度。
输入数据：输入的第一行是序列的长度N（1<=N<=1000）。第二行给出序列中的N个整数，这些整数的取值范围都是0~10000。
输出要求：最长上升子序列的长度。
输入样例：
7
1 7 3 5 9 4 8
输出样例：
4
思路：先初始化每个位置为1，即只选该单个元素
再每一个元素和该元素之前的每一个元素比较，若小于该元素，表示可以通过小的那个元素到该元素，则更新子序列长度加1
最后找到每个元素中最大子序列长度。
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
const double PI=acos(-1.0);
const int inf=0x7fffffff;
int a[105];
int dp[105];
int n,m,mx,sum;
int main(){
cin>>n;
mx=-inf;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
dp[i]=1; //初始化每个位置长度为1
for(int j=1;j<i;j++){
if(a[i]>a[j]){
dp[i]=max(dp[i],dp[j]+1);//可以经过小的那个元素dp[j]到dp[i],所以需要dp[j]+1
}
}
mx=max(mx,dp[i]);//mx为所有元素的子序列中最大的值
}
cout<<mx;
return 0;
}
(二维最大上升子序列) 套信封问题
给出 n 个信封的长 l 和宽 w ,某信封a的长和宽都小于信封b,则a信封可以套入b信封
求最多套入信封的层数？
思路:先对长可以先进行一个排序，然后对宽寻找最长上升子序列