首页 > 代码库 > 编程之美——longest incremental sequence(LIS)

编程之美——longest incremental sequence(LIS)

2024-07-18 13:44:26   223人阅读

解法一：通过遍历得到（0：i）的LIS，时间复杂度O(N^2)；

具体思路于代码，如下：

 1 #include<iostream> 2 #include<vector> 3 using namespace std; 4  5 int longSub(int arr[],int n); 6  7 int main() 8 { 9     int arr[8]={1,-1,2,-3,4,-5,6,-7};10     cout<<longSub(arr,8)<<endl;11     return 0;12 }13 14 int longSub(int arr[],int n)15 {16     vector<int>LIS;17 18     for(int i=0;i<n;++i)19     {20         //初始化默认长度为121         LIS.push_back(1);22         for(int j=0;j<i;++j)23         {24             //更新LIS[I]，得到LIS[I]最大值25             if(arr[i]>arr[j]&&LIS[j]+1>LIS[i])26                 LIS[i]=LIS[j]+1;27         }28     }29 30     int maxLis=0;31     //返回最大值32     for(int i=0;i<LIS.size();++i)33         if(LIS[i]>maxLis)34             maxLis=LIS[i];35 36     return maxLis;37 }
View Code

解法二：希望找到前i个元素的中的一个递增序列，使其中最大元素比arr[i]小，并且尽可能长；时间复杂度O(N^2)，若将其中查找改为二分查找，则时间复杂度O(N*logN)

代码如下：

 1 #include<iostream> 2 #include<vector> 3 using namespace std; 4  5 int longSub(int arr[],int n); 6 int minArr(int arr[],int n); 7  8 int main() 9 {10     int arr[8]={1,-1,2,-3,4,-5,6,-7};11     cout<<longSub(arr,8)<<endl;12     return 0;13 }14 15 int longSub(int arr[],int n)16 {17     //LIS：记录历史递增序列18     //maxV：记录历史递增序列中最大值19     vector<int>LIS;20     vector<int>maxV;21 22     maxV.push_back(minArr(arr,n)-1);23     maxV.push_back(arr[0]);24 25     //初始化最长递增序列长度26     int maxLIS=1;27 28     for(int i=1;i<n;++i)29     {30         //初始化31         LIS.push_back(1);32         int j;33 34         //更新得到最长LIS，时间复杂度O(N^2)35         for(j=maxLIS;j>=0;--j)36         {37             if(arr[i]>maxV[j])38             {39                 LIS[i]=j+1;40                 break;41             }42         }43 44           //如果当前最长序列大于最长递增序列长度，更新45         if(LIS[i]>maxLIS)46         {47             maxLIS=LIS[i];48             maxV[LIS[i]]=arr[i];49         }50         //更新maxV[j+1]，取较小值51         else if(arr[i]<maxV[j+1]&&arr[i]>maxV[j])52             maxV[j+1]=arr[i];53     }54     return maxLIS;55 }56 57 int minArr(int arr[],int n)58 {59     int tmp=arr[0];60     for(int i=0;i<n;++i)61         if(arr[i]<tmp)62             tmp=arr[i];63     return tmp;64 }
View Code

 


联系
我们