Lại là Dãy con liên tục khác biệt


Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

Cho dãy \(n\) phần tử \(a_1,a_2,...a_n\) tìm một dãy con liên tục nhiều phần tử nhất có thể sao cho trong dãy con đó không có bất kỳ 2 phần tử nào bằng nhau

Input

Dòng đầu gồm \(n\) là số phần tử của dãy ~(1 \le n \le 10^5)

Dòng cuối chứa \(n\) số nguyên không âm có giá trị không vượt quá \(10^9\)

Output

Một số tự nhiên duy nhất là độ dài của dãy con liên tục dài nhất thoải mãn không có cặp \(2\) phần tử bất kỳ nào bằng nhau

Ví dụ

Input

12
4 7 2 8 4 8 3 2 4 9 3 6

Output

5

Giải thích có hai dãy con liên tục có 5 số liên tiếp thỏa mãn như \(8, 3, 2, 4, 9\) hoặc \(2, 4, 9, 3, 6\)

tichpx

Comments


  • 1
    TICHPX  commented on June 27, 2020, 10:42 a.m.

    Code tham khảo

    #include<bits/stdc++.h>
    using namespace std;
    unordered_map<int,int> M;
    int main()
    {
        int n,x,t=0,res=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            if(M[x]>t) t=M[x];
            if(res<i-t) res=i-t;
            M[x]=i;
        }
        printf("%d",res);
    }

  • 1
    TICHPX  commented on June 26, 2020, 8:40 a.m.

    Chết mất thời gian 1s còn điểm thì 5 mình cho ngược


  • 1
    Phuc_CNTT3_K60  commented on June 26, 2020, 5:09 a.m.

    Thầy ơi sao bài này là phiên bản nâng cấp mà lại ít điểm hơn ạ =))