Published

25/05/2026

Modified

22/04/2026

Maior Subsequência Crescente (LIS)

O Problema Principal

O problema da Maior Subsequência Crescente (Longest Increasing Subsequence - LIS) é um clássico que qualquer programador competitivo deve carregar no peito.

O problema: Dada uma sequência \(S\) aleatória, descobrir o tamanho da maior cadeia cujos elementos só aumentam. Vale lembrar que uma subsequência não precisa possuir elementos consecutivos grudados na corda original; você pode ignorar/deletar números sobressalentes.

Por exemplo: \(S = \{3, 4, 3, 5, 2, 7\}\) * Uma subsequência crescente válida: \(\{3, 5, 7\}\) (Tamanho 3) * A Maior subsequência crescente: \(\{3, 4, 5, 7\}\) (Tamanho 4)

A Solução Visual \(\mathcal{O}(N \log N)\) (Algoritmo das Pilhas / Patience Sorting)

Imagine que você tem cartas de um baralho e quer separá-las em pilhas (ordenadas da esquerda para a direita). As regras de alocação de um novo número são:

  1. Pode empilhar em cima de uma pilha existente se a carta nova NÂO superar (for \(\le\)) à carta lá no topo.
  2. A carta vai SEMPRE na primeira pilha (mais à esquerda) que respeitar a Condição 1.
  3. Se o novo número for gigantesco e não couber em cima de nenhuma das pilhas atuais, crie uma Nova Pilha no final da mesa à direita.

O poder dessa máquina visual de separar cartas é colossal: O número total de pilhas ao final do algoritmo é o tamanho exato da LIS! Além disso, os topos lidos numa tacada garantem instâncias válidas de crescimento.

Visualização do Estado por Rodada

Na série \(\{3, 4, 3, 5, 2, 7\}\), observe as cartas sendo alocadas nos montes:

A Busca Binária no Vetor de Topos

Como a nossa inserção segue regras crescentes lineares, em competições, nós guardamos apens o “vetor de topos”. A busca pela “primeira pilha mais à esquerda que caiba” pode ser traduzida para \(\mathcal{O}(\log N)\) utilizando a clássica função iteradora lower_bound do C++. Esta função acha perfeitamente essa posição pra gente!

No código corrigido abaixo, guardamos o rastro físico dos pais para depois reconstituirmos fisicamente as respostas num vetor.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

// Retorna tanto o tamanho quanto OS ELEMENTOS da LIS fisicamente!
vector<int> calcular_lis(const vector<int> &v) {
    int N = v.size();
    if (N == 0) return {};

    // pilha guarda *os índices* originais na array cujos valores são os topos das pilhas
    vector<int> pilhaIndices; 
    vector<int> pai(N, -1); // De onde um número tirou base antes de pular para sua própria pilha

    for(int i = 0; i < N; i++) {
        // Encontra onde colocar o val = v[i] usando o valor mascarado no iterador
        int esq = 0, dir = pilhaIndices.size() - 1;
        int posInclusao = pilhaIndices.size();

        while (esq <= dir) {
            int meio = esq + (dir - esq) / 2;
            if (v[pilhaIndices[meio]] >= v[i]) {
                posInclusao = meio;
                dir = meio - 1;
            } else {
                esq = meio + 1;
            }
        }

        // Se está alocando em cima de uma pilha > 0 (ex: Pilha 2 ou 3),
        // Então ele cresceu com base no topo fixado anteriormente da pilha anterior (Pilha 1 ou 2)
        if (posInclusao > 0) {
            pai[i] = pilhaIndices[posInclusao - 1];
        }

        if (posInclusao == pilhaIndices.size()) {
            pilhaIndices.push_back(i); // Nova pilha
        } else {
            pilhaIndices[posInclusao] = i; // Substitui o topo antigo por v[i] (q é eq ou mais leve)
        }
    }

    // Atingimos a glória: recriamos o array usando Backtracking nos pais!
    vector<int> resposta;
    int curr = pilhaIndices.back(); // Pega a ponta da última estaca empilhada
    while (curr != -1) {
        resposta.push_back(v[curr]);
        curr = pai[curr];
    }
    reverse(resposta.begin(), resposta.end());

    return resposta;
}

void executando_testes() {
    // Cenário Metáfora do texto
    vector<int> sequencia = {3, 4, 3, 5, 2, 7};
    vector<int> respostaLis = calcular_lis(sequencia);
    
    // O tamanho das pilhas deve ser 4 e a sequencia física deve existir no vetor
    assert(respostaLis.size() == 4);
    
    // A cadeia que o backtrace acha pelo limite é 2, 4, 5, 7 ou 3, 4, 5, 7!
    // No nosso algoritmo ele esmagou o 3 da Pilha 1 com o 2! Então a base dele é o 2.
    assert((respostaLis == vector<int>{2, 4, 5, 7} || respostaLis == vector<int>{3,4,5,7}));

    cout << "[✅] LIS Patience Sorting log(N) validado com sucesso garantindo rastreio físico!\n";
}

int main() {
    executando_testes();
    return 0;
}

A complexidade final fica definida no \(\mathcal{O}(N \log N)\) garantindo execução instântanea mesmo para \(2 \times 10^5\) elementos.

Se a sua prova quiser números não-decrescentes (aceitar repetidos contíguos na mesma LIS, exemplo: 3, 3, 5), a nossa clássica lower_bound morre. Nós apenas trocamos a rotina interna por uma upper_bound, pois para entrar na mesma pilha e matar um valor, as regras de exclusividade são alteradas!

Exercício Prático

  • Resolva problemas clássicos de Longest Increasing Subsequence online. Um exemplo magistral da Neps/Beecrowd é o dos trens nos cruzamentos.
  • A LIS também pode cruzar a LCS que resolvemos anteriormente na aula 0025. Se ordenarmos um vetor, e submetermos ele em versão embaralhada contra ele memso ordenado num algoritmo LCS… a resposta da intersecção é magicamente uma LIS inteira (ainda que no formato arriscado do \(N^2\)). Explorar isso traz imenso calo analítico.
Back to top