Description
Input
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
Output
最长上升子序列的长度。
Sample Input
7
17 3 5 9 4 8
Sample Output
4
参考程序
#include <stdio.h>
#include <string.h>
#define LEN 1000
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int a[LEN+5],dp[LEN+5],N;
int i,j;
scanf("%d",&N);
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
dp[i]=1;
}
for(i=1;i<N;i++)
{
for(j=0;j<i;j++)
{
if(a[i]>a[j])
{
dp[i]=max(dp[j]+1,dp[i]);
//保证a[i]的前驱应比它小（并入序列后能成为一个上升序列），而且应该跟在dp值最大的元素后
}
}
}
int max=-1;
for(i=0;i<N;i++)
{
//求出dp数组中的最大值
if(dp[i]>max)
{
max=dp[i];
}
}
printf("%d\n",max);
return 0;
}
分析：这是一道动态规划问题的一道典型问题。关键问题是如何找到状态转移方程，即递推式。寻找递推式从只有一项元素的极端状态入手，逐步扩大规模发现规律。
设dp[i]表示以元素a[i]为结尾的最大递增子序列的长度.
如果只有一个元素，例如“3”，那默认为上升，即dp[0]=1.
如果有两个元素，例如“3 1”，这个序列本身就是递减的，所以1的存在并没有使得序列增长。或者说，a[i]作为某个序列的结尾，必须要添加在比它小的元素后边，这样能保证以元素a[i]为结尾的序列仍旧是递增的；然而在下标i之前，比a[i]小的元素可能有很多，那么究竟应该加在哪个元素后面呢？应当加在dp取最大值的所对应元素的后边，相当于强强联合，每一步都只并入上一步最长的序列（当然还要保证序列递增的前提下），递推下去，那么就能得出问题的全局解。
dp数组的求取借助了内外两层循环，因而算法的时间复杂度应为O(N^2)
希望大家批评指正！
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: