Subsequência crescente mais longa (LIS)
Escolha números de uma lista, da esquerda para a direita, cada um maior do que o anterior. Até que comprimento pode chegar uma cadeia assim? A pergunta é simples o suficiente para um livro de enigmas, e a sua resposta liga um jogo de cartas, uma tabela clássica de programação dinâmica e um dos resultados mais belos sobre baralhamentos aleatórios.
O problema
Dada uma lista de números, uma subsequência mantém alguns deles na sua ordem original. É crescente se cada valor for maior do que o anterior. A subsequência crescente mais longa, ou LIS, é a escolha mais longa deste tipo. Uma lista de n valores tem 2ⁿ subsequências, por isso verificá-las todas só funciona para listas muito curtas.
A tabela
Seja len[i] o comprimento da subsequência crescente mais longa que termina exatamente na posição i. Vale 1 para o valor sozinho, ou 1 + len[j] para uma posição anterior j cujo valor é menor, o que for maior. Cada posição olha para trás para todas as anteriores, por isso a tabela precisa de n·(n − 1)/2 comparações. A resposta é o maior len[i], e anotar que j deu cada len[i] permite ler a subsequência de trás para a frente.
Um exemplo
Tome 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Posição a posição, os comprimentos são 1, 2, 1, 1, 3, 2, 3, 4, 3 e 5: o 20 prolonga 3, 10; o 4 prolonga o 3; o 6 prolonga o 4, o 7 o 6 e o 9 o 7. Lendo de trás para a frente a partir do 9 obtém-se 3, 4, 6, 7, 9, uma subsequência crescente de comprimento 5.
Um método mais rápido: a ordenação por paciência
Distribua os valores como cartas em montes: cada valor vai para o monte mais à esquerda cujo topo não seja menor do que ele, ou começa um monte novo à direita. O número de montes é o comprimento da LIS. Como os topos dos montes estão sempre ordenados, o monte certo pode ser encontrado por pesquisa binária, por isso todo o método leva O(n log n) passos. Deve o nome ao jogo de paciência (solitário) com que se parece.
Um pouco de matemática
Em 1935, Paul Erdős e George Szekeres provaram que qualquer lista de n² + 1 números diferentes tem uma subsequência crescente ou decrescente de comprimento n + 1. Em 1961, Stanislaw Ulam perguntou qual é o comprimento da LIS de um baralhamento aleatório de n números. A resposta, próxima de 2√n para n grande, foi encontrada em 1977 por Anatoly Vershik e Sergei Kerov e por Ben Logan e Larry Shepp, e em 1999 Jinho Baik, Percy Deift e Kurt Johansson descobriram a forma exata das suas flutuações: a distribuição de Tracy–Widom da teoria das matrizes aleatórias.
Explore
Abra a aplicação e prima Avançar. A coluna laranja é a posição que está a ser calculada e a coluna azul a posição anterior com que é comparada. A linha Comprimento cresce à medida que se encontram cadeias mais longas, a linha Vem depois de lembra de onde vieram, e no fim a resposta é lida de trás para a frente a laranja e mostrada por baixo da tabela.
Perguntas frequentes
Qual é a complexidade temporal da LIS?
O(n²) com a tabela, porque cada posição olha para todas as anteriores, e O(n log n) com a ordenação por paciência e pesquisa binária. Ambos precisam de O(n) de memória.
Como encontro a subsequência não decrescente mais longa?
Deixe um valor vir depois de um valor igual: compare com ≤ em vez de <. Na aplicação, marque Permitir valores iguais. Com a ordenação por paciência, coloque cada valor no monte mais à esquerda cujo topo seja estritamente maior.
O que é a subsequência decrescente mais longa?
O mesmo problema com a comparação invertida, ou a LIS da lista com cada valor trocado de sinal. Pelo teorema de Erdős–Szekeres, uma lista suficientemente longa tem sempre uma subsequência crescente longa ou uma subsequência decrescente longa.
Qual é o comprimento da LIS de uma lista aleatória?
Para um baralhamento aleatório de n números diferentes, perto de 2√n para n grande. A correção cresce como a raiz sexta de n, por isso para mil números a média é cerca de 58, um pouco menos do que 2√1000 ≈ 63.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimente a subsequência crescente mais longa