微客导航 » 文章资讯 » C++计算整数序列的最长递增子序列的长度操作

C++计算整数序列的最长递增子序列的长度操作

2023-07-08 12:38:04 260

给定一个整数序列，计算其中的最长递增子序列的长度，这是一个典型的动态规划的算法。

比如8个整数的序列186186150200160130197200，最长递增子序列是150160197200,长度为4。

想要解决此问题，可以把这个大问题分解为小问题，依次考虑每个数，计算出包含该数数和该数之前的所有数的最长递增子序列的长度，计算出的长度值作为该数的对应值记录下来，最后可以得到这8个数对应的长度值序列，也是8个数，找到这8个数中的最大值就是所有书的最长递增子序列的长度。

或者也可以这样想，想要计算8个数的最长递增子序列的长度有难度，不如先考虑最简单的情况。只有一个数的时候，最长递增子序列长度就是1；当有两个数时，只考虑第一个数和它以前的数的最长递增子序列就是1，考虑第二个数时只需要找到它之前的所有数中比第二个数小的所有数中最长递增子序列的长度最大值然后加一，就是第二个数的长度。

下面给出实现代码：

#include
#include
#include
usingnamespacestd;
intfindLoogestIncreaseSeq(vector&vect)
{
intlen=0;
int*count=newint[vect.size()];
for(inti=0;i=0;j--)
{
if(vect[j]=count[i])
{
count[i]=count[j]+1;
}
}
if(count[i]>len)
len=count[i];
}
delete[]count;
returnlen;
}
intmain()
{
vectorvect;
inttemp;
while(cin>>temp)
{
vect.push_back(temp);
}
cout<
补充知识：C++求最长递增子序列（动态规划）



i
0
1
2
3
4
5
6
7
8


a[i]
1
4
7
2
5
8
3
6
9


lis[i]
1
2
3
2
3
4
3
4
5



时间复杂度为n^2的算法：
//求最长递增子序列
//2019/2/28
#include
usingnamespacestd;
intLIS(inta[],intN)
{
intlis[100]={};
for(inti=0;imax)
max=lis[i];//找出lis数组中最大值，即最长有序子序列的长度
}
returnmax;
}
intmain()
{
intN;
inta[100];
while(cin>>N)
{
for(inti=0;i>a[i];
cout<
以上这篇C++计算整数序列的最长递增子序列的长度操作就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。

返回顶部
3162201930
czq8825@qq.com

C++计算整数序列的最长递增子序列的长度操作

热门推荐

随机推荐