学习之动态规划
程序员文章站
2022-03-14 09:47:35
...
求最长子序列长度
问题描述:
上升序列(b1,b2,…,bn),当b1<b2<…<bn时,序列是上升的。给定一个序列(a1,a2,…an),可得到一些上升子序列(ai1,ai2,…aik),这里1<=i1<i2<…<ik<=n。一个序列,如(1,7,3,5,2,8),上升子序列有(1,3,5,8),(1,7,8)等等。子序列中最长的长度是4。设计算法求出一个数列的最长上升子序列长度。
输入:
第一行,输入数的个数,以下一行输入各个数。
输出:
最长子序列长度。
设备:
VC6.0或其他c语言编程软件
动态规划思路:
(1)将问题分成N个子问题(长度为N的序列)。
(2)以每个N为终点,判断子问题上升序列的长度。
(3)最后取最长上升子序列长度,得到整个问题的解。
具体方法(关键部分):
(1)数组从下标1开始存储。
(2)第一个上升子序列长度为1。 以后每一个考察两点:
- 上升子序列中,保证终点向左的每个数都小于终点N
- 在1.的前提下(b[a]>b[j]),记录子序列最大长度
(3)tmp在第二重循环前初置为0。记录最长长度。
(4)最后输出
代码:
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXV 1000
int b[MAXV+10];
int maxLen[MAXV+10];
int main()
{
int N;
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d",&b[i]);
maxLen[1]=1;
for(int a=2;a<=N;a++)
{
int temp=0;
for(int j=1;j<i;j++)
{
if(b[a]>b[j])
{
if(temp<maxLen[j])
temp=maxLen[j];
}
}
maxLen[a]=temp+1;
}
int maxL=-1;
for(int c=1;c<=N;c++)
if(maxL<maxLen[c])
maxL=maxLen[c];
printf("%d\n",maxL);
return 0
}
执行结果:
上一篇: 一个从别的网站抓取信息的例子(域名查询)