最长连续相异子序列 ----2014年湖南科技大学校赛

时间：2021-03-02 00:33:52

最长连续相异子序列

时间限制: 5 Sec   内存限制: 128 MB

题目描述

 给出一个含有n个数的序列，求一段最长的连续子序列的长度且这个子序列中不存在相同的数;

输入

题目由多组数据组成,不超过30组；每组数据由两行组成，第一行输入一个数n(0<n<=105)表示序列的长度；接下来一行是n个整数,每个数大于0且小于231;输入以EOF结尾。

输出

对于每组测试数据，输出一行表示最长连续相异子序列的长度；

样例输入

10 1 2 3 4 5 1 2 3 4 5 6 1 1 1 1 1 1

样例输出

5 1

提示


分析：

1、一开始以为是DP题，仔细一看，还不能用DP方法解决。

2、想了很久，没有想出什么巧方法，最后没办法就模拟人工操作解决。

3、10的5次方长度，所以一般的遍历（如加入2个for循环）就会超时，然后就想到DP那种思维去解决。

4、切入正题，读取一个数字就开始判断，这样虽然没有把复杂度减少好多，但这样比较好吧。我的思路拿个例子来说吧，比如12345345这个数列，当遍历到第二个3时，则前面的数量为5，即cnt=5，两个3之间为3，则拿5和3比较，然后把cnt=3，相当于123被舍去了，现在序列就是4开始的数列45345，则到3的数量便为cnt=3.

5、我的程序是把读入的数作为数组的角标，这样方便判断这个数在前面是否已经出现。但是，面对着这个题数据达到2的31次方，我始终没想出其他方法，不过，提交后还是AC了。


LANGUAGE：C++

CODE：

<span style="font-size:14px;">#include <iostream>
#include <string.h>
#include <limits.h>
#include <cmath>
using namespace std;
const int MAX_N=100005;
int used[MAX_N];

int main()
{
    //freopen("data.txt","r",stdin);
    int t[MAX_N];
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int max_=INT_MIN; //设max_为int型最小值
        int r=0,l=0;     //定义左区间l，右区间r
        int cnt=0;       //计数
        memset(used,0,sizeof(used));  //给used数组赋初始值0
        for(int i=1;i<=n;i++){
            cin>>t[i];
            if(!used[t[i]]||(used[t[i]]<r)&&l>used[t[i]]){  //输入一个数，如果输入的没有出现过或者当前这个数第一次
                used[t[i]]=i;
                cnt++;
            }
            else{
                max_=max(max(cnt,max_),i-used[t[i]]);  
                cnt=i-used[t[i]];
                l=used[t[i]];
                used[t[i]]=i;
                r=i;
            }
        }
        max_=max(max_,cnt);
        cout<<max_<<endl;
    }
}</span>




标签：

相关文章