11572 - Unique Snowflakes(two pointer)

Problem A: Unique Snowflakes

The marketing motto for the company is "bags of uniqueness." To live up to the motto, every snowflake in a package must be different from the others. Unfortunately, this is easier said than done, because in reality, many of the snowflakes flowing through the machine are identical. Emily would like to know the size of the largest possible package of unique snowflakes that can be created. The machine can start filling the package at any time, but once it starts, all snowflakes flowing 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 snowflakes have flowed out of the machine.

Input Specification

Sample Input

1
5
1
2
3
2
1

Output Specification

Output for Sample Input

3

题意：说白了就是求一个连续子序列最长没有相同数，

思路：两指针。l,r。r不断后移，每次记录下区间内数字的位置（利用map离散化）。然后如果出现num[r]在区间内，就把l指针后移到r的位置。不断维护最大值即可。

代码：

#include <stdio.h>
#include <string.h>
#include <map>
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;

const int N = 1000005;

int t, n, num[N];
map<int, int> vis;

void init() {
	vis.clear();
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &num[i]);
}

int solve() {
	int ans = 0;
	int l = 0;
	for (int r = 1; r <= n; r++) {
		if (vis[num[r]] > l) l = vis[num[r]];
		vis[num[r]] = r;
		ans = max(ans, r - l);
	}
	return ans;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		init();
		printf("%d\n", solve());
	}
	return 0;
}

11572 - Unique Snowflakes(two pointer)

原文：http://blog.csdn.net/accelerator_/article/details/18864443