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

时间:2020-12-10 na_beginning 人气:0

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

比如8个整数的序列 186 186 150 200 160 130 197 200，最长递增子序列是 150 160 197 200, 长度为4。

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

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

下面给出实现代码：

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
int findLoogestIncreaseSeq(vector<int> &vect)
{
 int len = 0;
 int *count = new int[vect.size()];
 for (int i = 0; i < vect.size(); i++)
 count[i] = 1;
 for (int i = 0; i < vect.size(); i++)
 {
 for (int j = i - 1; j >= 0; j--)
 {
 if (vect[j] < vect[i] && count[j] >= count[i])
 {
 count[i] = count[j] + 1;
 }
 }
 if (count[i] > len)
 len = count[i];
 }
 delete [] count;
 return len;
}
int main()
{
 vector<int> vect;
 int temp;
 while (cin >> temp)
 {
 vect.push_back(temp);
 }
 cout << findLoogestIncreaseSeq(vect) << endl;
 return 0;
}

补充知识：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<iostream>
using namespace std;
int LIS(int a[],int N)
{ 
 int lis[100] = {};
 for(int i =0;i<N;i++)//给每一个数的lis赋初值为1
 {
  lis[i]=1; 
 }
 for(int i = 1;i<N;i++)
 {
  for(int j =0;j<i;j++)
  {
   if(a[j]<a[i]&&lis[j]<lis[i]+1) //找出当前元素前面比它小的元素，比较其lis值
    lis[i] = lis[j] + 1;
  }
 }
 int max = lis[0];
 for(int i =1;i<N;i++)
 {
  if(lis[i]>max)
   max = lis[i];   //找出lis数组中最大值，即最长有序子序列的长度
 }
 return max;
}
int main()
{
 int N;
 int a[100];
 while(cin>>N)
 {
  for(int i = 0;i<N;i++)
   cin>>a[i];
  cout<<LIS(a,N)<<endl;
 }
 return 0;
}

以上这篇C++计算整数序列的最长递增子序列的长度操作就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。

加载全部内容