求整数数组中的最长递增子序列长度
发布时间
阅读量：
阅读量
昨天在复习软考的时候发现了这样的一个算法，有些地方确实经过一番推敲才搞懂，今天来整理记录一下~
动态规划通常用来求解最优化问题，在这类问题中，我们通过做出一组选择来达到最优解。在做出每个选择的同时，通常会生成与原问题形式相同的子问题。当多于一个选择子集都生成相同的子问题时，动态规划技术通常会很有效，其关键技术就是对每个这样的子问题都保存其解，当其重复出现时可以避免重复求解。---《算法导论》
题目求的是最长递增子序列的长度 ，而不是最长递增子序列 ，这就降低了解题难度。因为只要求出最优值，而不要求求出组成最优值的解。要说明的一点是：递增子序列中的数字不一定要在给定数组中是连续的，不知道大家的想法是不是跟我一样，我一开始就理解错了。eg: a={3,10,5,15,6,8}; 那么这个数组中的最长递增子序列是 3 5 6 8
题目中已经给出了方法描述：
假设数组a的长度为n，用数组b的元素b[i]记录以ai为结尾元素的最长递增子序列的长度为max{ b[i] },0<=i<n；其中b[i]满足最优子结构，可递归定义为：
b[0]=1;
b[i]=max{b[k]}+1 ,0<=k<n且a[k]<=a[i]
有了上面的描述，代码如下：
#include<stdio.h>
#include<string.h>
#include<ctype.h>
int find_max(int *b,int n)
{
int i,tmp=0;
for(i=0; i<n; i++)
{
if(tmp<b[i])
tmp=b[i];
}
return tmp;
}
int main()
{
int a[100];
int b[100];//b[i]用来存储以a[i]为结尾的最长递增子序列的长度max{b[i]},1<=i<n
b[0]=1;
int i,j,n;
int len;//记录递增子序列的长度
scanf("%d",&n);
int k;
for(k=0; k<n; k++)
scanf("%d",&a[k]);
for(i=1; i<n; i++)
{
for(j=0,len=0; j<i; j++)
{
if(a[j]<=a[i]&&len<b[j])
{
len=b[j];
}
}
b[i]=len+1;
}
printf("%d\n",find_max(b,n));
}对于如何求出最长递增子序列，只需要在动态规划的过程中用一个二维数组记录以a[i]为结尾的递增子序列即可。代码修改如下：
#include<stdio.h>
#include<string.h>
#include<ctype.h>
void find_max(int (*c)[100],int *b,int n)
{
int i,tmp=0;
for(i=0; i<n; i++)
{
if(tmp<b[i])
tmp=b[i];
}
int index=i-1;
printf("Len=%d\n",tmp);
for(i=0;i<tmp;i++){
printf("%d ",c[index][i]);
}
}
int main()
{
int a[100];
int b[100];//b[i]用来存储以a[i]为结尾的最长递增子序列的长度max{b[i]},1<=i<n
int c[100][100];//记录递增子序列
b[0]=1;
c[0][0]=a[0];
int i,j,n;
int len;//记录递增子序列的长度
scanf("%d",&n);
int k;
for(k=0; k<n; k++)
scanf("%d",&a[k]);
for(i=1; i<n; i++)
{
for(j=0,len=0,k=0; j<i&&k<i; j++)
{
if(a[j]<=a[i]&&len<b[j])
{
len=b[j];
c[i][k++]=a[j];
}
}
b[i]=len+1;
c[i][k]=a[i];
}
find_max(c,b,n);
}全部评论 (0)
还没有任何评论哟~