a bit of uva : UVa 11572 - Unique Snowflakes

Problem Statement:
UVa 11572 - Unique Snowflakes

Summary:
Find the maximum $|i-j|$ such that for a sequence $a_1,a_2,\ldots,a_n$, the subsequence $a_i, a_{i+1}, \ldots, a_j$ has distinct elements.

I like this problem, because it allows you to think a bit and reward you with happiness and joy (haha wth I'm writing that for). Strategy: Suppose we already have a subsequence $T = a_i, a_{i+1}, \ldots, a_j$. Upon deciding whether $a_{j+1}$ can be added to this subsequence, we need a quick way to check whether the previous occurrence of $v = a_{j+1}$ is before index i. Otherwise it's already in the subsequence, and therefore if there is a longer subsequence other than T, it must start after the occurrence of v in T (Proof by contradiction). By the end of this procedure, we will obtain the longest subsequence possible such that each element are all distinct.

There are various ways to get a fast look up for previous occurrences of an element: If $a_i$ are small, a simple array for direct addressing table (DAT) suffices. Otherwise, a good hash table with expected O(1) or a map with O(log N) look-up time will do.