Equipe Rust Brasil 10 min de leitura

Subsequência Crescente Mais Longa (LIS)

Implemente a Subsequência Crescente Mais Longa em Rust: solução O(n²) com DP, O(n log n) com busca binária e reconstrução da subsequência.

programação dinâmica lis subsequência busca binária rust

A Subsequência Crescente Mais Longa (LIS — Longest Increasing Subsequence) é um dos problemas clássicos de programação dinâmica. Dado um array de números, queremos encontrar a maior subsequência onde cada elemento é estritamente maior que o anterior (mantendo a ordem original). O LIS aparece em análise de séries temporais, otimização de compiladores, bioinformática, e é a base do algoritmo de ordenação “patience sort”.

Nesta página, apresentamos duas abordagens: a solução DP clássica O(n^2) e a solução otimizada O(n log n) usando busca binária, ambas com reconstrução da subsequência real.

O Problema

Entrada: Um array de inteiros arr[] de tamanho n.

Objetivo: Encontrar o comprimento da maior subsequência estritamente crescente. Uma subsequência mantém a ordem relativa, mas não precisa ser contígua.

Exemplo:

arr = [10, 9, 2, 5, 3, 7, 101, 18]

Subsequências crescentes:
  [2, 5, 7, 101]  comprimento 4  <-- LIS
  [2, 5, 7, 18]   comprimento 4  <-- também LIS
  [2, 3, 7, 101]  comprimento 4  <-- também LIS
  [10, 101]        comprimento 2
  [9, 101]         comprimento 2

Comprimento da LIS: 4

Abordagem Ingênua (Força Bruta)

Testamos todas as 2^n subsequências e verificamos quais são crescentes:

/// Força bruta: testa todas as subsequências.
/// Complexidade: O(2^n) — impraticável.
fn lis_bruta(arr: &[i32]) -> usize {
    fn resolver(arr: &[i32], pos: usize, anterior: i32) -> usize {
        if pos == arr.len() {
            return 0;
        }

        // Opção 1: pular o elemento atual
        let sem = resolver(arr, pos + 1, anterior);

        // Opção 2: incluir o elemento atual (se for maior que o anterior)
        let com = if arr[pos] > anterior {
            1 + resolver(arr, pos + 1, arr[pos])
        } else {
            0
        };

        sem.max(com)
    }

    resolver(arr, 0, i32::MIN)
}

fn main() {
    let arr = [10, 9, 2, 5, 3, 7, 101, 18];
    println!("LIS: {}", lis_bruta(&arr)); // 4
}

Identificando Subestrutura Ótima

Abordagem O(n^2)

Definimos dp[i] como o comprimento da LIS que termina no índice i:

dp[i] = 1 + max(dp[j]) para todo j < i onde arr[j] < arr[i]
dp[i] = 1 se nenhum j satisfaz a condição (o próprio elemento é uma LIS de tamanho 1)

Resposta: max(dp[i]) para todo i

Abordagem O(n log n)

Mantemos um array auxiliar tails[] onde tails[k] armazena o menor valor final possível dentre todas as subsequências crescentes de comprimento k+1:

Para cada elemento x do array:
  - Se x > tails[último]: estende a LIS, adiciona x ao final
  - Senão: encontra o menor tails[k] >= x e substitui por x (busca binária)

Visualização da Tabela DP

Abordagem O(n^2) para arr = [10, 9, 2, 5, 3, 7, 101, 18]:

Índice:   0    1    2    3    4    5    6    7
arr:     10    9    2    5    3    7  101   18
        +----+----+----+----+----+----+----+----+
dp:     |  1 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |  (inicialização)
        +----+----+----+----+----+----+----+----+

i=0: dp[0] = 1  (nenhum elemento anterior)
i=1: 9 > ? nenhum j com arr[j]<9 e j<1... espere, arr[0]=10>9, então dp[1]=1
i=2: 2 > ? nenhum anterior menor, dp[2]=1
i=3: 5 > 2 (j=2), dp[3] = dp[2]+1 = 2
i=4: 3 > 2 (j=2), dp[4] = dp[2]+1 = 2
i=5: 7 > 2 (j=2), 7 > 5 (j=3), 7 > 3 (j=4)
     dp[5] = max(dp[2], dp[3], dp[4]) + 1 = 2+1 = 3
i=6: 101 > todos anteriores
     dp[6] = max(dp[0..6]) + 1 = 3+1 = 4
i=7: 18 > 2,5,3,7  mas 18 < 101
     dp[7] = dp[5]+1 = 3+1 = 4

        +----+----+----+----+----+----+----+----+
dp:     |  1 |  1 |  1 |  2 |  2 |  3 |  4 |  4 |
        +----+----+----+----+----+----+----+----+

Resposta: max(dp) = 4

Abordagem O(n log n) — evolução do array tails:

Processando arr = [10, 9, 2, 5, 3, 7, 101, 18]:

Passo 1: x=10  tails=[]          -> tails=[10]
Passo 2: x=9   9<10, substitui   -> tails=[9]
Passo 3: x=2   2<9, substitui    -> tails=[2]
Passo 4: x=5   5>2, estende      -> tails=[2, 5]
Passo 5: x=3   3>2 mas 3<5, sub  -> tails=[2, 3]
Passo 6: x=7   7>3, estende      -> tails=[2, 3, 7]
Passo 7: x=101 101>7, estende    -> tails=[2, 3, 7, 101]
Passo 8: x=18  18>7 mas 18<101   -> tails=[2, 3, 7, 18]

Comprimento da LIS: tails.len() = 4

NOTA: tails NÃO é a LIS real! É apenas uma estrutura auxiliar
que mantém os menores valores finais possíveis.

Complexidade

AbordagemTempoEspaçoObservação
Força BrutaO(2^n)O(n) pilhaImpraticável
Top-Down (Memoização)O(n^2)O(n)Equivalente ao DP quadrático
Bottom-Up (DP O(n^2))O(n^2)O(n)Simples, bom para n <= 10^4
Otimizado (busca binária)O(n log n)O(n)Ideal para n grande

Implementação: Top-Down (Memoização)

use std::collections::HashMap;

/// LIS com memoização.
/// Cache: (posição, último valor incluído) -> comprimento da LIS.
fn lis_memo(
    arr: &[i32],
    pos: usize,
    anterior: i32,
    cache: &mut HashMap<(usize, i32), usize>,
) -> usize {
    if pos == arr.len() {
        return 0;
    }

    if let Some(&valor) = cache.get(&(pos, anterior)) {
        return valor;
    }

    // Opção 1: pular o elemento atual
    let sem = lis_memo(arr, pos + 1, anterior, cache);

    // Opção 2: incluir (se crescente)
    let com = if arr[pos] > anterior {
        1 + lis_memo(arr, pos + 1, arr[pos], cache)
    } else {
        0
    };

    let resultado = sem.max(com);
    cache.insert((pos, anterior), resultado);
    resultado
}

fn main() {
    let arr = [10, 9, 2, 5, 3, 7, 101, 18];
    let mut cache = HashMap::new();
    println!("LIS: {}", lis_memo(&arr, 0, i32::MIN, &mut cache)); // 4
}

Implementação: Bottom-Up (Tabulação)

Solução O(n^2)

/// LIS com DP O(n²) — bottom-up.
/// dp[i] = comprimento da LIS que termina no índice i.
fn lis_dp(arr: &[i32]) -> usize {
    let n = arr.len();
    if n == 0 {
        return 0;
    }

    // Cada elemento sozinho é uma LIS de tamanho 1
    let mut dp = vec![1usize; n];

    for i in 1..n {
        for j in 0..i {
            if arr[j] < arr[i] {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
    }

    // A resposta é o máximo do array dp
    *dp.iter().max().unwrap()
}

fn main() {
    let arr = [10, 9, 2, 5, 3, 7, 101, 18];
    println!("LIS: {}", lis_dp(&arr)); // 4

    let arr2 = [0, 1, 0, 3, 2, 3];
    println!("LIS: {}", lis_dp(&arr2)); // 4

    let arr3 = [7, 7, 7, 7, 7];
    println!("LIS: {}", lis_dp(&arr3)); // 1 (estritamente crescente)
}

Solução O(n log n) com Busca Binária

/// LIS com busca binária — O(n log n).
/// Mantém array `tails` com os menores valores finais de subsequências.
fn lis_binaria(arr: &[i32]) -> usize {
    let mut tails: Vec<i32> = Vec::new();

    for &x in arr {
        // Busca binária: posição do primeiro elemento em tails >= x
        let pos = tails.partition_point(|&t| t < x);

        if pos == tails.len() {
            // x é maior que todos os tails: estende a LIS
            tails.push(x);
        } else {
            // Substitui para manter o menor valor final possível
            tails[pos] = x;
        }
    }

    tails.len()
}

fn main() {
    let arr = [10, 9, 2, 5, 3, 7, 101, 18];
    println!("LIS (O(n log n)): {}", lis_binaria(&arr)); // 4

    let arr2 = [3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12];
    println!("LIS: {}", lis_binaria(&arr2)); // 6 (ex: [2, 4, 5, 6, 7, 12])

    // Array já ordenado: LIS = n
    let arr3 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    println!("LIS (ordenado): {}", lis_binaria(&arr3)); // 10

    // Array decrescente: LIS = 1
    let arr4 = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];
    println!("LIS (decrescente): {}", lis_binaria(&arr4)); // 1
}

Nota sobre partition_point: Este método da biblioteca padrão faz busca binária e retorna o índice onde a condição deixa de ser verdadeira. É equivalente a lower_bound em C++ e perfeito para nosso caso.

Otimização de Espaço

Ambas as abordagens (O(n^2) e O(n log n)) já usam O(n) de espaço, que é ótimo — precisamos de pelo menos O(n) para armazenar o array de entrada. O array tails na versão com busca binária nunca excede n elementos.

Reconstruindo a Solução

Reconstrução com DP O(n^2)

/// LIS com reconstrução da subsequência real.
fn lis_reconstruir(arr: &[i32]) -> Vec<i32> {
    let n = arr.len();
    if n == 0 {
        return Vec::new();
    }

    let mut dp = vec![1usize; n];
    // predecessor[i] = índice do elemento anterior na LIS que termina em i
    let mut predecessor = vec![None::<usize>; n];

    for i in 1..n {
        for j in 0..i {
            if arr[j] < arr[i] && dp[j] + 1 > dp[i] {
                dp[i] = dp[j] + 1;
                predecessor[i] = Some(j);
            }
        }
    }

    // Encontra o índice onde a LIS termina
    let mut melhor_idx = 0;
    for i in 1..n {
        if dp[i] > dp[melhor_idx] {
            melhor_idx = i;
        }
    }

    // Reconstrói percorrendo os predecessores
    let mut lis = Vec::new();
    let mut idx = Some(melhor_idx);
    while let Some(i) = idx {
        lis.push(arr[i]);
        idx = predecessor[i];
    }

    lis.reverse();
    lis
}

fn main() {
    let arr = [10, 9, 2, 5, 3, 7, 101, 18];
    let lis = lis_reconstruir(&arr);
    println!("LIS: {:?} (comprimento {})", lis, lis.len());
    // LIS: [2, 5, 7, 101] (comprimento 4) ou [2, 3, 7, 101]
}

Reconstrução com O(n log n)

/// LIS O(n log n) com reconstrução completa.
fn lis_binaria_reconstruir(arr: &[i32]) -> Vec<i32> {
    let n = arr.len();
    if n == 0 {
        return Vec::new();
    }

    let mut tails: Vec<i32> = Vec::new();
    // pos_na_lis[i] = comprimento da LIS terminando em arr[i] (0-indexado)
    let mut pos_na_lis = vec![0usize; n];
    // predecessor[i] = índice do elemento anterior na LIS
    let mut predecessor = vec![None::<usize>; n];
    // ultimo_idx[k] = índice em arr do elemento que ocupa tails[k]
    let mut ultimo_idx: Vec<usize> = Vec::new();

    for i in 0..n {
        let pos = tails.partition_point(|&t| t < arr[i]);

        if pos == tails.len() {
            tails.push(arr[i]);
            ultimo_idx.push(i);
        } else {
            tails[pos] = arr[i];
            ultimo_idx[pos] = i;
        }

        pos_na_lis[i] = pos;
        predecessor[i] = if pos > 0 {
            Some(ultimo_idx[pos - 1])
        } else {
            None
        };
    }

    // Reconstrói: encontra o último elemento da LIS mais longa
    let lis_len = tails.len();
    let mut resultado = Vec::with_capacity(lis_len);

    // Encontra o último índice usado na LIS completa
    let mut idx = Some(ultimo_idx[lis_len - 1]);
    while let Some(i) = idx {
        resultado.push(arr[i]);
        idx = predecessor[i];
    }

    resultado.reverse();
    resultado
}

fn main() {
    let arr = [10, 9, 2, 5, 3, 7, 101, 18];
    let lis = lis_binaria_reconstruir(&arr);
    println!("LIS (O(n log n)): {:?}", lis);

    let arr2 = [3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12];
    let lis2 = lis_binaria_reconstruir(&arr2);
    println!("LIS: {:?} (comprimento {})", lis2, lis2.len());
}

Patience Sorting — Conexão Visual

O algoritmo O(n log n) é baseado no jogo de cartas “patience” (paciência). Cada “pilha” corresponde a uma posição no array tails:

Cartas: [10, 9, 2, 5, 3, 7, 101, 18]

Pilha 1   Pilha 2   Pilha 3   Pilha 4
+-----+
| 10  |
+-----+
| 9   |
+-----+
| 2   |   +-----+
+-----+   | 5   |
           +-----+
| 3   |   |     |   +-----+
|(sub)|   |     |   | 7   |   +-----+
+-----+   +-----+   +-----+   | 101 |
                               +-----+
                     | 18  |
                     |(sub)|
                     +-----+

Número de pilhas = comprimento da LIS = 4

Exercícios Práticos

  1. LIS não-decrescente: Modifique para encontrar a subsequência não-decrescente mais longa (elementos iguais são permitidos). Dica: mude < para <= na busca binária.

  2. Número de LIS: Conte quantas LIS distintas existem (mesmo comprimento, mas diferentes subsequências). Mantenha um array extra count[i].

  3. LIS em 2D: Dadas coordenadas (x, y), encontre a maior cadeia onde x[i] < x[j] e y[i] < y[j]. Aplicação: problema dos envelopes russos (Russian Doll Envelopes).

  4. Menor número de subsequências decrescentes: Particione o array no menor número de subsequências estritamente decrescentes. Pelo teorema de Dilworth, a resposta é igual ao comprimento da LIS.

Veja Também