UVa 11572

链接：

 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2619

题意：

输入一个长度为n（n≤1e6）的序列A，找到一个尽量长的连续子序列A[L]～A[R]，使得该序列中没有相同的元素。

分析：

滑动窗口法。
假设序列元素从0开始编号，所求连续子序列的左端点为L，右端点为R。
首先考虑起点L=0的情况。可以从R=0开始不断增加R，相当于把所求序列的右端点往右延伸。
当无法延伸（即A[R+1]在子序列A[L～R]中出现过）时，只需增大L，并且继续延伸R。
既然当前的A[L～R]是可行解，L增大之后必然还是可行解，所以不必减少R，继续增大即可。
可以这样判断R是否可以延伸：
用一个map求出 last[i]，即下标i的“上一个相同元素的下标”。
例如，输入序列为3 2 4 1 3 2 3，当前区间是[1,3]（即元素2, 4, 1），是否可以延伸呢？
下一个数是A[4]=3，它的“上一个相同位置”是下标0（A[0]=3），不在区间中，因此可以延伸。

代码：

#include <cstdio>
#include <map>
using namespace std;

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n, ans = 0;
        scanf("%d", &n);
        map<int,int> last;
        for(int i, L = 0, R = 1; R <= n; R++){
            scanf("%d", &i);
            if(last[i] > L) L = last[i];
            if(ans < R - L) ans = R - L;
            last[i] = R;
        }
        printf("%d
", ans);
    }
    return 0;
}