Maior Subsequência Crescente
Aprenda DP O(n^2) e depois o truque O(n log n).
Maior Subsequência Crescente é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que é uma LIS
Uma subsequência mantém a ordem, mas ignora elementos. A subsequência crescente mais longa é a maior sequência desse tipo que cresce estritamente.
a = [3, 1, 4, 1, 5, 9, 2]Subsequência, não subvetor
Ao contrário de um subvetor, uma LIS não precisa ser contígua. Você pode saltar sobre números menores para manter a cadeia crescendo.
O estado da DP O(n^2)
Seja dp[i] o comprimento da LIS que termina no índice i. Todo elemento é, por si só, uma subsequência de comprimento um.
dp = [1] * nA transição O(n^2)
Para cada i, examine todos os j anteriores. Se a[j] for menor, estenda: dp[i] = max(dp[i], dp[j] + 1).
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)Leia a resposta
O resultado é o maior valor da tabela, pois a LIS pode terminar em qualquer posição, não apenas no último índice.
answer = max(dp)Por que O(n^2) pode causar TLE
O laço duplo custa O(n^2). Para n próximo de 100000, isso é lento demais e resulta em um veredito de limite de tempo.
A ideia da paciência
O método mais rápido mantém uma lista da menor cauda possível para cada comprimento de subsequência, como na ordenação por paciência.
tails = []Use a busca binária para posicionar
Para cada número, procure por busca binária onde ele se encaixa entre as caudas usando bisect_left, obtendo O(n log n) no total.
from bisect import bisect_leftEstenda ou substitua
Se a posição estiver depois do fim, use append para aumentar a LIS. Caso contrário, substitua essa cauda pelo valor menor.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xO comprimento está nas caudas
Quando a varredura termina, len(tails) é o comprimento da LIS. A própria lista nem sempre é a subsequência; somente seu comprimento é exato.
answer = len(tails)Estritamente crescente versus não decrescente
Para a variante não decrescente, troque para bisect_right, permitindo que valores iguais prolonguem a cadeia.
from bisect import bisect_rightVerificação rápida
Qual método encontra o comprimento da LIS em O(n log n)?
Recapitulação: de n^2 a n log n
Agora você consegue resolver LIS de duas formas. A DP O(n^2) é simples; o método de caudas mais busca binária escala para entradas grandes e supera o limite de tempo.
Perguntas Frequentes
A aula “Maior Subsequência Crescente” é grátis?
Sim — o texto completo de “Maior Subsequência Crescente” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Maior Subsequência Crescente”?
Aprenda DP O(n^2) e depois o truque O(n log n). Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Maior Subsequência Crescente”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Memoização versus Tabulação
- Defina o Estado e a Transição
- Subida de Escadas e Combinações de Moedas
- Maior Subsequência Crescente