Aula por Rogério Júnior
O problema da Maior Subsequência Crescente é um clássico que qualquer programador competitivo deve conhecer. Na aula 13 do Curso já havíamos abordado e resolvido este problema, mas em complexidade O(n²), enquanto podemos fazê-lo em O(n log n). O problema é: dada uma sequência s qualquer, descobrir o tamanho da maior subsequência crescente de s. Vale lembrar que uma subsequência de s é qualquer subconjunto de elementos de s. Veja, por exemplo:
s = {3, 4, 3, 5, 2, 7}
A maior subsequência crescente de s, neste caso é:
s' = {3, 4, 5, 7}
e tem tamanho 4.
Vamos primeiramente apresentar o algoritmo para depois explicarmos por que ele funciona.
Imagine que você tem uma sequência de números para distribuir em pilhas. As pilhas estão ordenadas da esquerda para a direita. Para cada novo número, você tem duas operações possíveis:
- Colocar o novo número no topo de uma pilha se ele não superar o que já está em seu topo;
- Criar uma nova pilha à direita de todas as outras e colocar o novo número lá.
Agora, suponha que sua meta é distribuir todos os números com a menor quantidade de pilhas possível. Para isso, você usará um algoritmo guloso e sempre colocará o número na pilha mais à esquerda em que ele pode ser colocado. Veja o exemplo com a sequência {3, 4, 3, 5, 2, 7}:
1. s: 3, 4, 3, 5, 2, 7
2. s: 4, 3, 5, 2, 7
Pilha 1: 3
3. s: 3, 5, 2, 7
Pilha 1: 3
Pilha 2: 4
4. s: 5, 2, 7
Pilha 1: 3, 3
Pilha 2: 4
5. s: 2, 7
Pilha 1: 3, 3
Pilha 2: 4
Pilha 3: 5
6. s: 7
Pilha 1: 2, 3, 3
Pilha 2: 4
Pilha 3: 5
8. s: Ø
Pilha 1: 2, 3, 3
Pilha 2: 4
Pilha 3: 5
Pilha 4: 7
Na representação acima, o topo de cada pilha é representado pelo seu elemento mais à esquerda. Observe que durante qualquer iteração do algoritmo, os topos das pilhas sempre formam uma subsequência crescente, justamente porque sempre insiro um número na pilha mais à esquerda possível. Deste modo, se insiro um número na pilha p, seu topo continuará menor que o de todas as pilhas à sua direita, pois ele diminui ou continua igual (regra 1) e continuará maior que o de todas as pilhas à esquerda (pois se o novo número fosse menor ou igual ao de alguma pilha anterior, seria inserido lá).
Agora, perceba o poder deste algoritmo tão simples: o número de pilhas ao final do algoritmo é o tamanho da maior subsequência crescente. Isso ocorre por um motivo bem simples: dentro de cada pilha, os números estão em ordem não crescente (por definição só adiciono um novo número se ele não superar o topo), logo não posso escolher dois números de uma mesma pilha para formarmos uma subsequência crescente!
Como só podemos escolher um número de cada pilha, no máximo, para formarmos uma subsequência crescente, sabemos que comprimento máximo da LIS é o número de pilhas, agora basta um exemplo com este comprimento. No entanto, já vimos que a qualquer instante da execução do algoritmo, os topos das pilhas representam uma subsequência crescente de s, logo, quando criamos a última pilha, os topos das cartas representavam a maior subsequência crescente de s!
Para implementarmos este algoritmo em O(n log n), basta que usemos uma busca binária para encontrarmos a pilha mais à esquerda cujo topo não supera o número que estamos inserindo. Para isso, vamos guardar apena o topo de cada pilha em um vector de nome pilha e usaremos uma função já implementada do C++: a lower_bound. Esta função recebe o começo e o fim de um array ordenado, um elemento x e retorna um ponteiro para a posição mais à esquerda do array que não é menor que x.
Deste modo, a implementação é muito simples e auto-explicativa. O código abaixo, por exemplo, resolve o seguinte problema: dada uma entrada com um inteiro n seguido de uma sequência de n números, imprima o tamanho da maior subsequência crescente.
E se quisermos, além do tamanho, que o programa imprima alguma das maiores subsequências crescentes? É muito simples. Lembre-se que toda vez que adicionamos um elemento na última pilha, os topos das pilhas representam a maior subsequência crescente encontrada até agora. Assim, basta que, toda vez que inserimos um novo elemento nas pilhas, guardemos um ponteiro para a posição na sequência original do topo da pilha anterior a ele. Façamos também que o pai de qualquer elemento na primeira pilha seja -1. Deste modo, basta salvarmos o topo da última pilha, seu pai, o pai de seu pai e assim por diante, até encontrarmos o valor -1 em um vector resp, invertê-lo (usarei a função reverse) e imprimi-lo.
Note que, agora, temos que guardar a sequência no vector seq. Além disso, iremos guardar a posição original na sequência do topo de cada pilha no vetor pos (pos[i] guarda a posição original na sequência do elemento no topo da pilha i (pilha[i])), e o pai de cada elemento no vetor pai (pai[i] guarda o pai do elemento i da sequência original). Outro detalhe necessário é que agora precisamos saber o número, a posição da pilha em que iremos adicionar o novo número, visto que antes só tínhamos um ponteiro pra tal pilha. Porém o C++ facilita isso com operações entre iteradores: se it aponta para um elemento de um vector, basta subtrairmos de it o ponteiro para o começo do vector e teremos a posição de it. Deste modo, se it aponta para um elemento de pilha, a posição deste elemento é it - pilha.begin().
Segue o código, simples e auto-explicativo novamente:
Note que, no algoritmo, principal, temos apenas um loop que se repete n vezes, no qual a operação mais demorada é a chamada do lower_bound, de complexidade O(log n), logo a complexidade é n * O(log n) = O(n log n).
Vale lembrar que para encontrar a maior sequência não decrescente, ou seja, que aceite elementos repetidos, basta mudar uma regra do algoritmo: podemos inserir um número em uma pilha se seu topo não for menor ou igual ao número, ou seja, basta repetirmos exatamente o mesmo código trocando o lower_bound pelo upper_bound.
Agora que você já sabe tudo isso de LIS, tente fazer os problemas abaixo. Se você não conseguir resolver algum deles, ou surgir dúvida na teoria apresentada na aula, volte para a página inicial do curso para preencher o formulário e nos enviar sua dúvida.
Problema 1 - Easy Longest Increasing Subsequence
Problema 2 - Wavio Sequence
As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.