首页 > 代码库 > 编程之美——longest incremental sequence(LIS)
编程之美——longest incremental sequence(LIS)
解法一:通过遍历得到(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 }
解法二:希望找到前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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。