给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数N。
第二行包含N个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤10001≤N≤1000，
−109≤数列中的数≤109−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
思路:根据动态转移方程，取每次循环遍历的后最后一个a[i]结尾的单调上升的序列的最大值，最后对每一类的最大值在进行Max
时间复杂度:O（n^2）
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 const int N = 1e5; 5 int n; 6 int a[N]; 7 int f[N]; 8 int main(){ 9 scanf("%d",&n); 10 for(int i = 1;i <= n;i++) scanf("%d",&a[i]); 11 for(int i = 1;i <= n;i++){ 12 f[i] = 1; 13 for(int j = 1;j < i;j++)
//动态转移方程 14 if(a[i] > a[j]) f[i] = max(f[i],f[j] + 1); 15 } 16 17 int res = 0; 18 for(int i = 1;i <= n;i++) res = max(res,f[i]); 19 printf("%d",res); 20 } 21