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.