算法：UVa 11572 - Unique Snowflakes （好题）

算法：UVa 11572 - Unique Snowflakes （好题）2014-03-17 csdn博客 shuangde800题目大意：

给n个数， n<=100W，求一个连续子序列，这个子序列中没有重复的数，问这个子序列最长是多少？

思路：

开一个数组pos， pos[ x ] 表示x出现的位置，这个数组初始化为-1

用一个变量start来记录当前枚举序列的起点，初始为0

然后枚举这个序列，依次记录每个数的位置，

假设当前枚举到i，在记录这个位置之前，先检查当前这个数的位置pos【 arr【i】】是否大于等于start，如果大于，说明这个数已经在[start, i-1]中已经出现过了，记下这个满足条件的子序列长度。然后枚举下一个子序列： start = pos[i] + 1. 这个算法总复杂度为O（n）

代码：

/** UVa 11572 Unique Snowflakes**/#include<iostream>#include<cstdio>#include<cstring>using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f;const int MAXN = 1000010;int arr[MAXN];int pos[MAXN];int main（）{int nCase, m, n;scanf（"%d", &nCase）;while（nCase--）{scanf（"%d", &n）;int cnt=0;for（int i=0; i<n; ++i）scanf（"%d", &arr[i]）;memset（pos, -1, sizeof（pos））;int start = 0;int maxx = 0;arr[n] = arr[n-1];for（int i=0; i<=n; ++i）{if（pos[arr[i]] >= start）{int tmp = i - start;maxx = max（tmp, maxx）;start = pos[arr[i]]+1;pos[arr[i]] = i;}else{pos[arr[i]] = i;}}printf（"%d
", maxx）;}return 0; }