Longest Increasing Subsequence
Você recebe uma lista de números inteiros nums. Uma subsequência mantém alguns dos elementos, na ordem original, e descarta os demais; os elementos mantidos não precisam estar lado a lado. Retorne o comprimento da subsequência mais longa cujos valores aumentam estritamente da esquerda para a direita. Dois valores iguais em sequência não contam como aumento.
Função
- numsinteger-array
- a lista de números inteiros para escolher
- Retornainteger
- o comprimento da maior subsequência estritamente crescente
Restrições
1 ≤ nums.length ≤ 2500-104 ≤ nums[i] ≤ 104
Exemplos
- Entrada
- nums = [3, 1, 8, 2, 5, 9, 4, 7]
- Saída
- 4
- Explicação
- Manter 1, 2, 5, 9 resulta em uma subsequência crescente de comprimento 4, assim como 1, 2, 5, 7 e 1, 2, 4, 7. Nenhuma escolha de cinco valores continua crescendo, então a resposta é 4.
- Entrada
- nums = [7, 7, 7, 7]
- Saída
- 1
- Explicação
- Os valores devem aumentar estritamente, então nenhum par de 7 pode estar na mesma subsequência. Um único elemento conta, o que faz com que a resposta seja 1.
- Entrada
- nums = [12, -4, 0, 25, -10, 3, 16, 5]
- Saída
- 4
- Explicação
- -4, 0, 3, 16 tem comprimento 4 (-4, 0, 3, 5 também tem). Começando pelo primeiro elemento, 12, você obtém apenas dois valores, como 12, 25: a melhor subsequência não precisa começar no início.
+20 testes ocultos ao enviar
Para ir além
Você consegue retornar uma subsequência crescente mais longa, e não apenas seu comprimento, ainda executando em O(n log n)?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
A melhor subsequência da lista inteira é difícil de descrever diretamente. Faça uma pergunta mais específica para cada índice
i: qual é a subsequência crescente mais longa que termina exatamente comnums[i]?Uma subsequência que termina em
nums[i]é formada apenas pornums[i]ou continua a melhor subsequência que termina em algumnums[j] < nums[i]anterior. Escolha o melhorjdesse tipo e some um. A resposta é o maior desses valores, independentemente de onde termina.Para ficar abaixo de
O(n²), mantenha, para cada comprimento, apenas o menor valor com que uma subsequência desse comprimento pode terminar. Esses valores permanecem ordenados, então uma busca binária informa se um novo número prolonga a subsequência mais longa ou substitui um valor final.
Solução
Uma subsequência pode pular qualquer elemento, então uma lista de n números tem 2^n subsequências, muitas demais para verificar. A solução com programação dinâmica é fazer uma pergunta mais específica para cada índice: qual é o comprimento da melhor subsequência crescente que termina exatamente aqui? Isso resulta em uma tabela O(n²). A versão mais rápida mantém um número por comprimento: o menor valor com que uma subsequência desse comprimento pode terminar, e posiciona cada novo elemento com uma busca binária.
Pegue ou pule cada elemento
Correta, mas não termina nos maiores testes
Intuição
Percorra a lista e tome uma decisão por elemento: mantê-lo ou deixá-lo de fora. Você só pode manter nums[i] quando ele for maior que o último valor mantido. Uma função recursiva longest(i, prev) responde: se o último elemento mantido estiver no índice prev (ou -1 quando nada foi mantido ainda), quantos elementos mais você pode adicionar a partir do índice i?
Pular resulta em longest(i+1, prev). Manter, quando isso é permitido, resulta em 1 + longest(i+1, i). A resposta é o maior dos dois valores, e, depois do fim da lista, nada mais pode ser adicionado, então o resultado ali é 0. Toda subsequência crescente corresponde a um caminho de escolhas de manter e pular, portanto a busca não pode deixar de encontrar a melhor.
É lento porque os dois ramos continuam abertos sempre que os valores aumentam. Em uma lista como 1, 2, 3, ..., n, as chamadas dobram a cada elemento: 2 elevado a 40 já representa cerca de 10^12 chamadas, e os testes grandes têm 2500 elementos. No entanto, longest(i, prev) depende apenas do par (i, prev), então há no máximo n² perguntas diferentes. Fazer cada pergunta uma única vez é a próxima abordagem.
Algoritmo
- Escreva
longest(i, prev), em queprevé o índice do último elemento mantido ou-1. - Se
iestiver além do fim, retorne 0. - Ignore
nums[i]:best = longest(i+1, prev). - Se
prevfor-1ounums[i] > nums[prev], mantenha-o:best = max(best, 1 + longest(i+1, i)). - Retorne
best. A resposta élongest(0, -1).
def lengthOfLIS(nums):
def longest(i, prev):
# The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
# prev is -1 while nothing has been taken.
if i == len(nums):
return 0
best = longest(i + 1, prev) # skip nums[i]
if prev == -1 or nums[i] > nums[prev]:
best = max(best, 1 + longest(i + 1, i)) # take nums[i]
return best
return longest(0, -1)Subsequência mais longa que termina em cada índice
Intuição
Estado. Seja ending[i] o comprimento da subsequência crescente mais longa cujo último elemento é nums[i]. Fixar o último elemento é o que permite dividir o problema de forma clara: quando você sabe onde uma subsequência termina, sabe quais valores posteriores podem vir depois dela.
Recorrência. Se a subsequência que termina em nums[i] tem mais de um elemento, o elemento anterior a nums[i] é algum nums[j] com j < i e nums[j] < nums[i], e a parte até ele deve ser a mais longa possível. Portanto, ending[i] = 1 + max(ending[j]) considerando esses valores de j. Caso base: cada elemento sozinho é uma subsequência, então ending[i] começa em 1. Ordem: ending[i] consulta apenas índices menores, então preencha da esquerda para a direita.
Para [3, 1, 8, 2, 5, 9, 4, 7], a tabela é [1, 1, 2, 2, 3, 4, 3, 4]. Por exemplo, 5 pode vir depois de 3, 1 ou 2, e o melhor desses valores é 2, com ending = 2; portanto, ending[4] = 3. A resposta é o maior valor da tabela, 4, não o último: a melhor subsequência pode terminar em qualquer posição.
Cada índice consulta todos os índices anteriores uma vez, então o trabalho corresponde a n(n-1)/2 comparações, cerca de 3.1 × 10^6 para n = 2500.
Algoritmo
- Crie
endingcom todas as entradas definidas como 1. - Para cada
i, da esquerda para a direita, examine todos osj < i. - Se
nums[j] < nums[i], definaending[i]comoending[j] + 1quando esse valor for maior. - Retorne o maior valor em
ending.
def lengthOfLIS(nums):
n = len(nums)
# ending[i]: the longest increasing subsequence that ends with nums[i]
ending = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
ending[i] = ending[j] + 1
return max(ending)Menores caudas com busca binária
Intuição
A tabela acima armazena um comprimento por índice. Você pode armazenar menos: para cada comprimento, apenas o menor valor com o qual uma subsequência crescente desse comprimento pode terminar. Chame-o de tails[k] para o comprimento k+1. Um valor final menor é sempre pelo menos tão bom, pois qualquer valor que possa vir depois de uma subsequência terminada em 9 também pode vir depois de uma terminada em 5.
tails está sempre ordenado em ordem estritamente crescente: uma subsequência de comprimento k+2 terminada em t contém uma de comprimento k+1 que termina abaixo de t. Portanto, para cada novo valor x, faça uma busca binária pelo primeiro valor em tails que seja ≥ x. Se não houver nenhum, x é maior que todos os valores em tails e estende a subsequência mais longa, então adicione-o. Caso contrário, substitua esse valor por x: a subsequência um elemento mais curta termina abaixo de x, então adicionar x produz o mesmo comprimento com um valor final menor.
Para [3, 1, 8, 2, 5, 9, 4, 7], tails fica [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7], e seu comprimento 4 é a resposta. Na etapa [1, 2, 4, 9], o 4 apareceu depois do 9 na entrada, então tails não é, por si só, uma subsequência; apenas seu comprimento tem significado. O método também é chamado de ordenação por paciência, em referência ao jogo de cartas em que cada valor final é a carta do topo de uma pilha.
Para cada elemento, é feita uma busca binária em no máximo n valores em tails: cerca de 2500 × 12 = 30.000 etapas para a maior entrada.
Algoritmo
- Comece com uma lista vazia
tails. - Para cada
xemnums, faça uma busca binária pelo primeiro índicekcomtails[k] ≥ x. - Se não houver nenhuma cauda
≥ x, acrescentex. - Caso contrário, defina
tails[k] = x. - Retorne o comprimento de
tails.
from bisect import bisect_left
def lengthOfLIS(nums):
# tails[k]: the smallest last value of any increasing subsequence of length k + 1
tails = []
for x in nums:
k = bisect_left(tails, x) # the first tail that is >= x
if k == len(tails):
tails.append(x) # x extends the longest subsequence so far
else:
tails[k] = x # x is a smaller ending for length k + 1
return len(tails)
Armadilhas e casos extremos
A maioria das respostas erradas acontece por confundir o que a tabela armazena ou por tratar valores iguais como crescentes.
- Retornar
ending[n-1]em vez da maior entrada. Para[1, 2, 3, 0], a última entrada é 1, mas a resposta é 3. - Comparar usando
≤em vez de<.[7, 7, 7, 7]deve retornar 1, não 4. - Na versão com tails, procurar o primeiro tail
> xem vez de≥ x. Com valores duplicados, isso acrescenta o segundo 7 depois do primeiro e conta valores iguais como uma subsequência mais longa. - Tratar
tailscomo a própria subsequência. Seus valores podem vir de subsequências diferentes, então imprima-a somente se você acompanhar os pais separadamente. - Resolver por engano a versão contígua. Em
[3, 1, 8, 2, 5, 9, 4, 7], a maior sequência crescente de elementos vizinhos é 2, 5, 9 (comprimento 3), enquanto a resposta é 4. - Em Lua e R, os arrays começam em 1, então um marcador
prev = -1baseado em índices a partir de 0 passa a ser 0, e a busca binária percorre os índices de 1 até o tamanho atual.
Perguntas frequentes4
Qual é a complexidade de tempo da subsequência crescente mais longa?
O método tails é executado em O(n log n) e usa O(n) de espaço: uma busca binária por elemento. A tabela de programação dinâmica que considera todos os pares de índices leva O(n²), e testar cada subsequência leva O(2ⁿ). Para n = 2500, isso corresponde a cerca de 30.000, 3 milhões e um número astronômico de etapas.
Por que o método de ordenação por paciência fornece o comprimento correto?
Após cada elemento, tails[k] contém o menor valor com que qualquer subsequência crescente de comprimento k+1 encontrada até então pode terminar. A adição ocorre apenas quando x é maior que todos os valores em tails, o que significa que agora existe uma subsequência com comprimento maior em um elemento do que qualquer subsequência anterior. A substituição nunca altera o comprimento; ela apenas diminui um valor final, então o comprimento da lista é sempre o comprimento da maior subsequência crescente.
Como obter a subsequência crescente mais longa propriamente dita, e não apenas seu comprimento?
Registre um pai para cada elemento. Na tabela O(n²), o pai de i é o j que atribuiu seu valor a ending[i]. No método das caudas, armazene o índice do elemento atrás de cada cauda e defina o pai de um elemento como o índice armazenado uma posição à sua esquerda quando ele for inserido. Em seguida, percorra os pais de volta a partir do fim da subsequência mais longa e inverta o resultado.
Como encontrar, em vez disso, a subsequência não decrescente mais longa?
Permita vizinhos iguais. Na tabela, use nums[j] ≤ nums[i]. No método tails, procure a primeira cauda que seja estritamente maior que x, em vez de maior ou igual, para que um valor igual estenda a lista em vez de substituir uma cauda. [7, 7, 7, 7] retorna 4.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def lengthOfLIS(nums):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
nums = [3, 1, 8, 2, 5, 9, 4, 7]
Esperado
4