Emily the entrepreneur has a cool business idea: packaging and selling snow

akes. She has devised a

machine that captures snow

akes as they fall, and serializes them into a stream of snow

akes that

ow,

one by one, into a package. Once the package is full, it is closed and shipped to be sold.

The marketing motto for the company is \bags of uniqueness." To live up to the motto, every

snow

ake in a package must be different from the others. Unfortunately, this is easier said than done,

because in reality, many of the snow

akes

owing through the machine are identical. Emily would like

to know the size of the largest possible package of unique snow

akes that can be created. The machine

can start lling the package at any time, but once it starts, all snow

akes

owing from the machine

must go into the package until the package is completed and sealed. The package can be completed

and sealed before all of the snow

akes have

owed out of the machine.

Input

The rst line of input contains one integer specifying the number of test cases to follow. Each test

case begins with a line containing an integer n, the number of snow

akes processed by the machine.

The following n lines each contain an integer (in the range 0 to 109, inclusive) uniquely identifying a

snow

ake. Two snow

akes are identied by the same integer if and only if they are identical.

The input will contain no more than one million total snow

akes.

Output

For each test case output a line containing single integer, the maximum number of unique snow

akes

that can be in a package.

整体思路是用滑动窗口，每次对一段区间[i,j]操作后，左指针+1，再把右指针尽量后移，得到尽量长的区间。关键是如何判断右指针什么时候该停止，即判断一个区间是否可行。

1 #include
     
       2 #include
      
     

以上为做法一。用nlogn时间求出上一个与之相同的元素的坐标last[i]，然后右指针右移直到它的last超过左指针。

求last的过程中，用map存储元素上一次出现的位置，边扫描边更新。

1 #include
     
       2 #include
      
        3 using namespace std; 4 int a[1000100]; 5 int max(int a,int b) 6 { 7     return a>b?a:b; 8 } 9 int main()10 {11     int i,j,k,m,n,p,q,x,y,z,ans,T;12     scanf("%d",&T);13     while (T--)14     {15         set
       
         s;16         scanf("%d",&n);17         for (i=1;i<=n;i++)18           scanf("%d",&a[i]);19         ans=-1;20         i=j=1;21         while (j<=n)22         {23             while (j<=n&&!s.count(a[j])) s.insert(a[j++]);24             ans=max(ans,j-i);25             s.erase(a[i++]);26         }27         printf("%d\n",ans);28     }29 }
       
      
     

以上为做法二。用set存储一个元素当前是否存在。左指针左移时删除元素，右指针右移时加入元素。