快捷導(dǎo)航

C++計算整數(shù)序列的最長遞增子序列的長度操作

更新時間：2020年12月10日 08:41:36 作者：na_beginning

這篇文章主要介紹了C++計算整數(shù)序列的最長遞增子序列的長度操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧

給定一個整數(shù)序列，計算其中的最長遞增子序列的長度，這是一個典型的動態(tài)規(guī)劃的算法。

比如8個整數(shù)的序列 186 186 150 200 160 130 197 200，最長遞增子序列是 150 160 197 200, 長度為4。

想要解決此問題，可以把這個大問題分解為小問題，依次考慮每個數(shù)，計算出包含該數(shù)數(shù)和該數(shù)之前的所有數(shù)的最長遞增子序列的長度，計算出的長度值作為該數(shù)的對應(yīng)值記錄下來，最后可以得到這8個數(shù)對應(yīng)的長度值序列，也是8個數(shù)，找到這8個數(shù)中的最大值就是所有書的最長遞增子序列的長度。

或者也可以這樣想，想要計算8個數(shù)的最長遞增子序列的長度有難度，不如先考慮最簡單的情況。只有一個數(shù)的時候，最長遞增子序列長度就是1；當(dāng)有兩個數(shù)時，只考慮第一個數(shù)和它以前的數(shù)的最長遞增子序列就是1，考慮第二個數(shù)時只需要找到它之前的所有數(shù)中比第二個數(shù)小的所有數(shù)中最長遞增子序列的長度最大值然后加一，就是第二個數(shù)的長度。

下面給出實(shí)現(xiàn)代碼：

#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;
}

補(bǔ)充知識：C++ 求最長遞增子序列（動態(tài)規(guī)劃）

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

時間復(fù)雜度為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++)//給每一個數(shù)的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) //找出當(dāng)前元素前面比它小的元素，比較其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數(shù)組中最大值，即最長有序子序列的長度
 }
 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++計算整數(shù)序列的最長遞增子序列的長度操作就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: