输入数据:
10
2 8 10 1 5 1 7 8 6 5
输出数据:
4
- #include <stdio.h>
- int main()
- {
- int a[1000],g[1000];
- int i,k,n,max;
-
- scanf("%d",&n);
- for(i=1;i<=n;i++) scanf("%d",&a[i]);
- //动规边界,初始化
- g[1]=1;
- //动规开始
- for(i=2;i<=n;i++)
- {
- g[i]=1;//初值,这里很用重要。。。。。位置不要写错,要在for(j)循环的外面
- //每次找i前面所有的数,所以是1到i-1
- for(k=1;k<=i-1;k++)
- {
- //枚举前面的每个数是不是比当前这个数小, 注意这里是不下降子序列,所以是小于等于
- if( a[i] <= a[k])
- {
- if( g[i] < g[k]+1 )
- g[i] = g[k] + 1;
- }
- }
- }
- //g 数组里面找最大的1个
- max=0;
- for(i=1;i<=n;i++)
- {
- if( max < g[i] )
- max = g[i];
- }
- printf("%d",max);
- return 0;
- }
复制代码
|