Informática Técnicas de programação - Maior Subsequencia Crescente (LIS) - Método 2 de calcular LIS (DP)

Aula por Caique Paiva

Conhecimento prévio necessário:

O intuito dessa aula é resolver o seguinte problema:

Dado uma sequência $a_1, a_2, \cdots , a_n$ , ache o tamanho da maior subsequência crescente de $a$ .

Por exemplo, na sequência $\{ 1, 3, 7 ,2, 5, 4, 10 \}$ , a maior subsequência crescente é $\{ 1, 3, 5, 10 \}$ , logo a resposta é $4$ . Vamos fazer $N \le 2 \cdot 10^5$ e $a_i \le 10^9$ para todo $i$ .

Vamos achar um algoritmo que roda em $O(n \log )$ com uma dp, e a melhor parte desse algoritmo é que podemos aplicar a mesma ideia para outros problemas.

A dp será a seguinte: Defina como $dp(x)$ para ser a maior subsequênca crescente no qual último valor dessa subsequência é $x$ . A ideia do problema é começar a calcular essa dp no intervalo $[1, 1]$ , e depois passar para o intervalo $[1, 2]$ , depois para o intervalo $[1, 3]$ , e ir até o intervalo $[1, n]$ .

Com isso, suponha que calculamos essa dp para o intervalo $[1, i]$ , então, vamos calcular ela para o intervalo $[1, i+1]$ . Primeiro, veja que o único valor da dp que nós vamos mudar é o de $dp[a_{i+1}]$ , pois as outras subsequências (Ou seja, as que não terminam em $a_{i+1}$ ) estão inclusas em $[1, i]$ . Com isso, vamos atualizar $dp[a_{i+1}]$ .

Com isso, para toda subsequência crescente que acaba em um número $x \le a_{i+1}$ , então, se incluirmos o $a_{i+1}$ nela, conseguimos uma subsequência crescente que acaba em $a_{i+1}$ , e ela vai ter tamanho máximo de $dp(x)+1$ ! Além disso, se $x \ge a_{i+1}$ , não podemos incluir $a_{i+1}$ na subsequência, ou seja, não contamos esse caso na dp. Portanto, a fórmula para calcular essa transição vai ser

$dp(a_{i+1}) = max_{1 \le x \le a_{i+1}} (dp(x)) + 1$

Porém, temos dois problemas nessa solução, mas eles são tranquilos de resolver:

Primeiro é o fato de que $a_i \le 10^9$ . Isso é um problema, pois precisamos criar um vetor para $dp$ de tamanho $max (a_i)$ , que pode ser igual a $10^9$ , resultando num MLE. Para resolver isso, basta fazer uma compressão de coordenadas, fazendo $a_i \le N$ .
O segundo problema é que, para calcular $max_{1 \le x \le a_{i+1}} dp(x)$ , fazemos um algoritmo em $O(a_{i+1})$ , ou seja, calcular essa dp é em $O(N^2)$ . Para resolver isso, basta ver que, se fizermos uma segtree de máximo, e então, em cada passo, calculamos a query de $[1, a_{i+1}]$ , e fazemos o update de $a_{i+1}$ como descrito acima, e então, a transição fica $O(log n)$ .

Com isso, achamos o algoritmo em $O(Nlog)$ .

Clique aqui para ver o código