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.

Uma fila de barras de alturas diferentes com uma cadeia ascendente delas destacada a laranja, da esquerda para a direita
Uma fila de barras de alturas diferentes com uma cadeia ascendente delas destacada a laranja, da esquerda para a direita

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.

Paul Erdős num seminário de estudantes em Budapeste, em 1992. Em 1935, ele e George Szekeres provaram que qualquer lista de n² + 1 números distintos tem uma subsequência crescente ou decrescente de comprimento n + 1.
Paul Erdős num seminário de estudantes em Budapeste, em 1992. Em 1935, ele e George Szekeres provaram que qualquer lista de n² + 1 números distintos tem uma subsequência crescente ou decrescente de comprimento n + 1.
Retrato de Stanisław Ulam
Retrato de Stanisław Ulam

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