- A preencher
- Lida
- Resposta
Subsequência crescente mais longa (LIS)
Numa lista de números, quantos consegue escolher, mantendo a sua ordem, de modo que cada um seja maior do que o anterior? A subsequência crescente mais longa responde a essa pergunta. Escreva uma lista e veja a programação dinâmica calcular, para cada posição, a cadeia mais longa que termina ali. Prima Reproduzir para ver a tabela a encher-se, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Escreva uma lista de números. Para cada posição, a tabela guarda o comprimento da cadeia crescente de valores mais longa que termina ali, e a posição anterior que ela continua. Marque Permitir valores iguais para cadeias que nunca descem. No fim, a cadeia é lida de trás para a frente a partir do seu último valor. Novo exemplo cria outra lista. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.
Como funciona
- Escreva uma lista de números, separados por vírgulas ou espaços. Marque Permitir valores iguais para cadeias que nunca descem.
- Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto.
- Veja cada posição ser comparada com todas as anteriores e depois veja a cadeia mais longa lida de trás para a frente a laranja.
Como funciona a tabela
A tabela tem três linhas: os valores, o comprimento da subsequência crescente mais longa que termina em cada posição e a posição que ela continua. Um valor sozinho é uma cadeia de comprimento 1. Depois, cada posição anterior é verificada: se o seu valor for menor, a cadeia que termina ali pode ser prolongada com este valor, ficando com mais um de comprimento. Ganha o prolongamento mais longo, e a sua posição vai para a terceira linha.
Ler a cadeia de trás para a frente
A subsequência crescente mais longa termina na posição com o maior comprimento. A partir daí, a terceira linha diz que posição vem antes, e a terceira linha dessa posição diz qual vem antes dela, até chegar a uma posição sem antecessor. Lidos por ordem, esses valores são a resposta. Com Permitir valores iguais marcado, um valor também pode vir depois de um valor igual, o que dá a cadeia mais longa que nunca desce.
Perguntas frequentes
Qual é a diferença entre uma subsequência e um subarray?
Um subarray é um bloco de valores vizinhos. Uma subsequência mantém a ordem mas pode saltar valores, por isso em 3, 10, 2, 1, 20 os valores 3, 10 e 20 formam uma subsequência crescente, embora 2 e 1 estejam entre eles.
Quão rápido é o algoritmo LIS?
O método da tabela compara cada par de posições: n·(n − 1)/2 comparações para n valores. A ordenação por paciência fá-lo em O(n log n): guarda, para cada comprimento, o menor valor que termina uma cadeia desse comprimento, e coloca cada valor novo por pesquisa binária.
A subsequência crescente mais longa é única?
Nem sempre. Em 1, 3, 2, 4, tanto 1, 3, 4 como 1, 2, 4 têm comprimento 3. A tabela dá o comprimento, e a leitura de trás para a frente encontra uma delas.
Onde se usa a subsequência crescente mais longa?
Na comparação de ficheiros e genomas, onde alguns métodos encontram primeiro as linhas correspondentes e depois tomam uma subsequência crescente das suas posições; no planeamento e em quebra-cabeças de empilhar caixas; e na matemática, onde o comprimento da LIS de um baralhamento aleatório é um objeto de estudo famoso.
Algum dado é enviado para algum lado?
Não. Tudo é calculado no seu navegador, e as suas últimas definições ficam guardadas no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor