Solução escrita por João Pedro Castro
Podemos exemplificar esse problema para: “ache o tamanho do maior intervalo contínuo dentro de um array com todos os valores distintos”, e para resolver esse problema podemos usar a ideia de guardar a última posição que cada valor apareceu, e depois fazer contas simples para atualizar a maior quantidade de valores distintos em um intervalo terminando na posição atual.
Vamos usar a ideia de um array 1-indexado, e inicializar o vetor $$u$$ (ultima vez que um valor apareceu) como 0, e com o tamanho $$S + 1$$. Também vamos criar uma varíavel com o tamanho do intervalo terminando na posição $$i$$ atual, chamaremos esse valor de $$d$$. Agora, para cada valor $$X_i$$ rodamos:
- Se $$u[X_i]$$ estiver dentro do intervalo atual ($$\geq i – d$$), logo, adicionar ele de novo quebraria as regras:
- $$d := d – (u[X_i] – (i – d) + 1)$$, ou seja, tiramos do tamanho a parte que vai do começo até a última vez que $$X_i$$ apareceu.
- $$d := d + 1$$ (o tamanho aumenta em 1, pois adicionamos o $$X_i$$ ao final do intervalo)
- $$u[X_i] = i$$
Agora fica claro que a resposta vai ser o $$d$$ máximo entre todas as posições $$i$$.