Maior Subsequência Crescente
O problema da Maior Subsequência Crescente é um clássico que qualquer programador competitivo deve conhecer. 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}:
s: 3, 4, 3, 5, 2, 7
s: 4, 3, 5, 2, 7
Pilha 1: 3
- s: 3, 5, 2, 7
Pilha 1: 3
Pilha 2: 4
- s: 5, 2, 7
Pilha 1: 3, 3
Pilha 2: 4
- s: 2, 7
Pilha 1: 3, 3
Pilha 2: 4
Pilha 3: 5
- s: 7
Pilha 1: 2, 3, 3
Pilha 2: 4
Pilha 3: 5
- 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 sequê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 sequência crescente de s, logo, quando criamos cada pilha, o topo da pilha anterior é o elemento que o precede em um exemplo de LIS 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, exemplifica uma função que recebe como parâmetro o endereço de um vector de inteiros e retorna o tamanho da maior subsequência crescente desse vetor.
#include <algorithm> // lower_bound
#include <vector> // vector
using namespace std;
#define PB push_back // por simplicidade
int lis(vector<int> &v){
vector<int> pilha; // declaro o vector que guardará o topo de cada pilha
// para cada elemento v[i] da sequência
for(int i=0; i<v.size(); i++){
// declaro um iterador que guardará o elemento mais à esquerda de pilha
// que não é menor que v[i]
vector<int>::iterator it = lower_bound(pilha.begin(), pilha.end(), v[i]);
// se it for o fim do vector, então não há elemento que não seja menor que v[i]
// ou seja, todos os topos de pilha são menores ou iguais a v[i]
// logo, criamos uma nova pilha e colocamos x no seu topo
if(it==pilha.end()) pilha.PB(v[i]);
// porém, se it apontar para alguma posição válida do vector
// colocamos v[i] no topo desta pilha, substintuindo o valor que it aponta por v[i]
else *it = v[i];
}
return pilha.size();
}
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 estão em ordem crescente. Assim, basta que, toda vez que inserirmos 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, 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. Agora, ele mostra uma função que recebe o endereço de um vector de inteiros e retorna outro vector, com um exemplo de maior subsequência crescente do original.
#include <algorithm> // lower_bound
#include <vector> // vector
using namespace std; // para uso do C++
#define PB push_back // por simplicidade
#define MAXN 100100 // defino o valor de MAXN
vector<int> lis(vector<int> &v){
// declaro s variáveis que vou usar
vector<int> pilha, resp;
int pos[MAXN], pai[MAXN];
// para cada elemento
for(int i=0; i<v.size(); i++){
// declaro um iterador que guardará o elemento mais à esquerda de pilha
// que não é menor que v[i]
vector<int>::iterator it = lower_bound(pilha.begin(), pilha.end(), v[i]);
// guardo a posição da pilha em que adicionarei o elemento
int p = it-pilha.begin();
// se it for o fim do vector, então não há elemento que não seja menor que v[i]
// ou seja, todos os topos de pilha são menores ou iguais a v[i]
// logo, criamos uma nova pilha e colocamos x no seu topo
if(it==pilha.end()) pilha.PB(v[i]);
// porém, se it apontar para alguma posição válida do vector
// colocamos v[i] no topo desta pilha, substintuindo o valor que it aponta por v[i]
else *it = x;
// a posição original na sequência do número no topo da pilha p agora é i
pos[p]=i;
// se o elemento foi inserido na primeira pilha
if(p==0) pai[i]=-1; // seu pai será -1
// caso contrário, seu pai será a posição do elemento no topo da pilha anterior a ele
else pai[i]=pos[p-1];
}
// p será a posição do elemento no topo da última pilha
int p = pos[pilha.size()-1];
// enquanto p não for -1
while(p>=0){
// adiciono o elemento na posição p à resposta
resp.PB(v[p]);
// e vou para o pai de p
p=pai[p];
}
// inverto a ordem da resposta
reverse(resp.begin(), resp.end());
// por fim, retorno o vetor resp
return resp;
}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.