UVa 11572 - Unique Snowflakes Solution

http://tonancos.com/3nM1

Tags: greedy

First, you make a set and start from the beginning of the array. As you move up the array making a segment, insert the numbers into the set. If you find that there's a duplicate element in the segment (using the set), from the bottom, delete the elements before the number from the set so that there's no more duplicates in the segment. From all the lengths you compute during this process, get the maximum.

Example 1:
6
1 2 2 3 2 1

(i is the current index we're on)
i = 0:
add 1 to the set
set = {1}

i = 1
add 2 to the set
set = {1, 2}

i = 2
you already have 2 in the set, so delete the numbers up until the earliest 2
set = {2} (deleted 1)

i = 3
set =  {2, 3}

i = 4
you already have 2 again, so delete the elements before the earliest 2, which is just 2

i = 5
set = {2, 3, 1}

---------------------------------------
Example 2:
6
1 2 3 4 5 5

i = 0
add 1 to the set
set = {1}

i = 1
set = {1, 2}

i = 2
set = {1, 2, 3}

i = 3
set = {1, 2, 3, 4}

i = 4
set = {1, 2, 3, 4, 5}

i = 5
we already have 5, so we'll delete all elements before last 5
set = {5}