1576 最长严格上升子序列
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
给一个数组a1, a2 … an，找到最长的上升降子序列ab1< ab2 < … < abk，其中b1< b2<..bk。
输出长度即可。
输入描述 Input Description
第一行，一个整数N。
第二行 ，N个整数（N < = 5000）
输出描述 Output Description
输出K的极大值，即最长不下降子序列的长度
样例输入 Sample Input
5
9 3 6 2 7
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
【样例解释】
最长不下降子序列为3,6,7
#include <stdio.h>
#include <stdlib.h>#define f(x) (*(data+x))int *data;
int length;
int n;void dp(int num,int last,int s)
{if(num==n){if(s>length){length=s;}return;}if(f(num)>last){dp(num+1,f(num),s+1);}dp(num+1,last,s);return;
}
int main()
{int i;scanf("%d",&n);data=(int*)malloc(sizeof(int)*n);for(i=0;i<n;i++)scanf("%d",data+i);dp(0,0,0);printf("%d\n",length);return 0;
}