Longest Increasing Subsequence

Q: 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 com todos os pares de índices leva O(n²) , e testar cada subsequência leva O(2ⁿ) .

Q: 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 estritamente maior que x , para que um valor igual estenda a lista em vez de substituir uma cauda. [7, 7, 7, 7] então retorna 4.

MédioProgramação dinâmica Busca binária

+10

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 crescentes.

Função

lengthOfLIS(nums: integer-array) → integer

numsinteger-array: a lista de números inteiros para escolher
Retornainteger: o comprimento da subsequência estritamente crescente mais longa

Restrições

1 ≤ nums.length ≤ 2500
-10⁴ ≤ nums[i] ≤ 10⁴

Exemplos

Entrada: nums = [3, 1, 8, 2, 5, 9, 4, 7]
Saída: 4
Explicação: 1, 2, 5, 9 é crescente, assim como 1, 2, 5, 7 e 1, 2, 4, 7: comprimento 4. Nenhuma escolha de cinco valores continua crescente.

Para ir além

Você consegue retornar uma das subsequências crescentes mais longas, além do seu comprimento, e ainda executar em O(n log n) de tempo?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Uma lista de n números tem 2^n subsequências, muitas demais para verificar. Perguntar, para cada índice, qual é o tamanho da melhor subsequência crescente que termina exatamente ali resulta em uma tabela O(n²). A versão mais rápida mantém, para cada tamanho, o menor valor com o qual uma subsequência desse tamanho pode terminar e posiciona cada elemento com uma busca binária.

Incluir ou pular cada elemento

Correta, mas não termina nos maiores testes

Intuição

Decida, para cada elemento, se deve mantê-lo; você só pode manter nums[i] quando ele for maior que o último valor mantido. longest(i, prev) é o maior número de elementos que você ainda pode adicionar a partir do índice i, quando o último elemento mantido está em prev (ou -1). Pular resulta em longest(i+1, prev); manter resulta em 1 + longest(i+1, i). Toda subsequência crescente corresponde a um caminho dessas escolhas.

Em 1, 2, 3, ..., n, os dois ramos continuam abertos e as chamadas dobram a cada elemento: 2^40 já é cerca de 10^12. Ainda assim, há no máximo n² pares diferentes (i, prev).

Algoritmo

Escreva longest(i, prev), em que prev é o índice do último elemento mantido, ou -1.
Se i estiver além do fim, retorne 0.
Ignore nums[i]: best = longest(i+1, prev).
Se prev for -1 ou nums[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)

Maior subsequência que termina em cada índice

Intuição

Seja ending[i] o comprimento da subsequência crescente mais longa cujo último elemento é nums[i]. O elemento antes de nums[i], se houver, é 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]) para esses j, ou 1 quando não houver nenhum. 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]: 5 pode vir depois de 3, 1 ou 2, e o melhor desses tem comprimento 2, então ending[4] = 3. A resposta é o maior valor, já que a melhor subsequência pode terminar em qualquer posição.

n(n-1)/2 comparações: cerca de 3.1 × 10^6 para n = 2500.

Algoritmo

Crie ending com todas as entradas definidas como 1.
Para cada i, da esquerda para a direita, examine cada j < i.
Se nums[j] < nums[i], defina ending[i] como ending[j] + 1 quando 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

Para cada comprimento, mantenha apenas o menor valor com que uma subsequência crescente desse comprimento pode terminar: tails[k] para o comprimento k+1. Um término menor nunca é pior: tudo o que pode vir depois de um 9 também pode vir depois de um 5. tails permanece estritamente crescente: remova o último valor de uma subsequência crescente de comprimento k+2 e você obtém uma de comprimento k+1 que termina com um valor menor.

Para cada x, faça uma busca binária pelo primeiro valor em tails que seja ≥ x. Se não houver nenhum, acrescente x: ele estende a subsequência mais longa. Caso contrário, substitua esse valor por x: a subsequência de um comprimento a menos termina com um valor menor que x, então x produz o mesmo comprimento com um término menor.

Por exemplo, no exemplo 1, tails fica [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7]: comprimento 4. Em [1, 2, 4, 9], o 4 veio depois do 9, então somente o comprimento de tails tem significado.

Algoritmo

Comece com uma lista vazia tails.
Para cada x em nums, faça uma busca binária pelo primeiro índice k em que tails[k] ≥ x.
Se nenhuma cauda for ≥ x, adicione x.
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

Retornar ending[n-1] em vez da maior entrada. Para [1, 2, 3, 0], a última entrada é 1, mas a resposta é 3.
Comparar com ≤ em vez de <. [7, 7, 7, 7] deve retornar 1, não 4.
Na versão com tails, procurar o primeiro tail > x em vez de ≥ x. O segundo 7 é então acrescentado depois do primeiro, contando valores iguais como crescentes.
Resolver por engano a versão contígua. No exemplo 1, a sequência crescente mais longa de elementos vizinhos é 2, 5, 9 (comprimento 3), enquanto a resposta é 4.
Manter índices baseados em 0 em Lua ou R, onde os arrays começam em 1. O marcador prev = -1 passa a ser 0, e a busca binária percorre os índices de 1 até o tamanho atual.

Perguntas frequentes3

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 com todos os pares de índices leva O(n²), e testar cada subsequência leva O(2ⁿ).

O que é ordenação por paciência na subsequência crescente mais longa?

É o método das caudas, que recebe esse nome por causa de um jogo de cartas. Cada cauda é a carta do topo de uma pilha: uma carta vai para a pilha mais à esquerda cujo topo tenha valor pelo menos igual ao dela, ou inicia uma nova pilha. O número de pilhas é a resposta.

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 estritamente maior que x, para que um valor igual estenda a lista em vez de substituir uma cauda. [7, 7, 7, 7] então retorna 4.

def lengthOfLIS(nums):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

nums = [3, 1, 8, 2, 5, 9, 4, 7]

Saída Esperada

Longest Increasing Subsequence

Função

Restrições

Exemplos

Dicas

Solução

Incluir ou pular cada elemento

Maior subsequência que termina em cada índice

Menores caudas com busca binária

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos