给一个数组a1, a2 ... an，找到最长的上升降子序列ab1<ab2< .. <abk，其中b1<b2<..bk。
输出长度即可。
第一行，一个整数N。
第二行 ，N个整数（N < = 5000）
输出K的极大值，即最长不下降子序列的长度
5
9 3 6 2 7
3
【样例解释】
最长不下降子序列为3,6,7
解题思路
参考：北大郭炜老师
1.找子问题：“求以ak（ k=1, 2, 3…N）为终点的最长上升子序列的长度”
一个上升子序列中最右边的那个数，称为该子序列的“终点”。
虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。
2. 确定状态
子问题只和一个变量-- 数字的位置相关。因此序列中数的位置k 就是“状态”，而状态 k 对应的“值”，就是以a[k]做为“终点”的最长上升子序列的长度。状态一共有N个。
3. 找出状态转移方程
maxLen [k]表示以a[k]做为“终点”的最长上升子序列的长度那么：
初始状态： maxLen [1] = 1
maxLen[k]= max { maxLen [i]： 1<=i < k 且 a[i ]< a[k]且 k≠1 } + 1
若找不到这样的i,则maxLen[k] = 1
maxLen[k]的值，就是在a[k]左边，“终点”数值小于a[k] ，且长度最大的那个上升子序列的长度再加1。因为a[k]左边任何“终点”小于a[k]的子序列，加上a[k]后就能形成一个更长的上升子序列 。
1 #include <stdio.h>
2 #define maxN 5005
3 int n,a[maxN],maxLen[maxN];//maxLen[k]表示以a[k]做为“终点”的最长上升子序列的长度
4 int main(int argc, char *argv[])
5 {
6 int i,j;
7 scanf("%d",&n);
8 for(i=0;i<n;i++) { scanf("%d",&a[i]); maxLen[i]=1; }
9
10 for(i=1;i<n;i++)//枚举所有子序列的终点
11 {
12 for(j=0;j<i;j++)//枚举以a[i]做终点的子序列中a[i]的前缀元素
13 {
14 if(a[j]<a[i])//尝试用a[j]做a[i]的直接前缀形成新的子序列
15 {
16 maxLen[i]=(maxLen[j]+1>maxLen[i]?maxLen[j]+1:maxLen[i]);
17 }
18 }
19 }
20 printf("%d\n",maxLen[n-1]);
21 return 0;
22 }
上面的代码写错了，抱歉。更正如下：
#include <stdio.h>
#define maxN 5005
int main(int argc, char *argv[])
{
int i,j,t;
int n,a[maxN],maxLen[maxN];//maxLen[k]表示以a[k]做为“终点”的最长上升子序列的长度
int max; scanf("%d",&n);
for(i=;i<n;i++) { scanf("%d",&a[i]); maxLen[i]=; }
for(i=;i<n;i++)//枚举所有子序列的终点
{
for(j=;j<i;j++)//枚举以a[i]做终点的子序列中a[i]的前缀元素
{
if(a[j]<a[i])//尝试用a[j]做a[i]的直接前缀形成新的子序列
{
maxLen[i]=(maxLen[j]+>maxLen[i]?maxLen[j]+:maxLen[i]);
}
}
}
max=maxLen[];
for(i=;i<n;i++)
if(maxLen[i]>max) max=maxLen[i];
printf("%d\n",max);
return ;
}
思考题 ： 如何改进程序，使之能够输出最长上升子序列 ？
思路：新增pre[ ]，其中pre[k]=x表示在a[ ]序列构成的若干个上升子序列中，a[k]的前驱是a[x]。一开始pre[ ]全部初始化为-1表示一开始所有元素的前驱都是自己本身。在循环求解maxLen[i]的同时，更新pre[i]。最后在扫描出maxLen[ ]最大值为maxLen[i]以后，从pre[i]往前推即可。假如要顺序输出该最长上升子序列，可以把逆推pre[ ]的过程保存再输出。
参考代码：
#include<stdio.h>
#include<string.h>
#define maxN 5005
int main(int argc, char *argv[])
{
int i,j,t;
int n,a[maxN],maxLen[maxN];//maxLen[k]表示以a[k]做为“终点”的最长上升子序列的长度
int max;
int pre[maxN];
int c[maxN],maxIndex; memset(pre,-,sizeof(pre)); scanf("%d",&n);
for(i=;i<n;i++) { scanf("%d",&a[i]); maxLen[i]=; } for(i=;i<n;i++)//枚举所有子序列的终点
{
for(j=;j<i;j++)//枚举以a[i]做终点的子序列中a[i]的前缀元素
{
if(a[j]<a[i])//尝试用a[j]做a[i]的直接前缀形成新的子序列
{
if(maxLen[j]+>maxLen[i])
{
maxLen[i]=maxLen[j]+;
pre[i]=j;
}
}
}
}
max=maxLen[];
for(i=;i<n;i++)
if(maxLen[i]>max) { max=maxLen[i]; maxIndex=i; }
printf("%d\n",max); j=;
c[j++]=a[maxIndex];
while(pre[maxIndex]!=-)
{
maxIndex=pre[maxIndex];
c[j++]=a[maxIndex];
}
for(i=j-;i>=;i--)
{
printf("%d ",c[i]);
}
printf("\n");
return ;
}
输出最长上升子序列的另一种思路：
#include <stdio.h>
int n,size,a[][],s,ans,next;
int main(int argc, char *argv[])
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
int t;
scanf("%d",&t);
a[i][]=t;a[i][]=;a[i][]=;
//a[i][1]表示以a[i][0]开头的最长上升子序列的长度。
//a[i][2]表示在以a[i][0]开头的最长上升子序列中a[i][0]的下一个数在原序列中的下标。
} for(int i=n-;i>=;i--)
{
size=next=;
for(int j=i+;j<n;j++)
if(a[j][]>a[i][]&&a[j][]>size) {size=a[j][];next=j;}
if(size>) {a[i][]=size+;a[i][]=next;}
} ans=;
for(int i=;i<n;i++)
if(a[i][]>a[ans][]) ans=i; printf("%d\n",a[ans][]); /*for(int i=0;i<n;i++)
printf("%d %d %d %d\n",a[i][0],a[i][1],a[i][2],i);*/ int i=ans;
while(a[i][]>)
{
printf("%d ",a[i][]);
i=a[i][];
}
printf("%d\n",a[i][]);
return ;
}
测试OJ地址：