首页 > 代码库 > 最长子序列

最长子序列

2024-07-16 14:35:16   218人阅读

在给定的序列中寻找最长的无重复子序列；

利用map<int,int>object标记每个数字的序号，如果这个数字重复过，那么就能确定他们之间的一个序列长度，然后起点更新到出现的重复的点上，

从这个点开始向后再次找无重复序列，然后每次对比它的长度和上一次确定的序列的长度，如果新序列的长度大于前一个长度就更新它，并且更新终点。

 

 1 #include<iostream> 2 #include<map> 3 using namespace std; 4 const int N=120; 5 int array[N]; 6 int starti,endi,start; 7 int main() 8 { 9     int n;10     while(cin>>n)11     {12         map<int,int>my_map;13         for(int i=1;i<=n;i++)14         {15             cin>>array[i];16         }17         int l=0,temp;18         starti=endi=start=1;19         for(int i=1;i<=n;i++)20         {21             if(my_map[array[i]]!=0)22             {23                 temp=my_map[array[i]]+1;24                 if(start<temp)start=temp;//如果起点向前了，就更换新的起点 25             }26             else if(l<i-start+i)//如果在新的起点到现在点距离大于原来的长度，就更新长度和终点27             {28                 l=i-start+1;29                 endi=i;30             }31             my_map[array[i]]=i;32         }33         cout<<l<<endl;34         cout<<"startpoint: "(endi-l)<<" endpoint: "<<endi<<endl;35     }36     return 0;37 }

 


联系
我们