Casquinha CF-OBI 2023 Solução

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$.

Clique aqui para ver o código