--- title: "Subsequência Crescente Mais Longa (LIS)" url: "https://rustlang.com.br/algoritmos/longest-increasing-subsequence/" markdown_url: "https://rustlang.com.br/algoritmos/longest-increasing-subsequence.MD" description: "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." date: "2026-02-24" author: "Equipe Rust Brasil" --- # 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. 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: ```rust /// 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 | Abordagem | Tempo | Espaço | Observação | |-----------|-------|--------|------------| | Força Bruta | O(2^n) | O(n) pilha | Impraticá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) ```rust 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) ```rust /// 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 ```rust /// 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 = 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) ```rust /// LIS com reconstrução da subsequência real. fn lis_reconstruir(arr: &[i32]) -> Vec { 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::; 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) ```rust /// LIS O(n log n) com reconstrução completa. fn lis_binaria_reconstruir(arr: &[i32]) -> Vec { let n = arr.len(); if n == 0 { return Vec::new(); } let mut tails: Vec = 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::; n]; // ultimo_idx[k] = índice em arr do elemento que ocupa tails[k] let mut ultimo_idx: Vec = 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 - [Vec — Vetores dinâmicos](/stdlib/vec/) — base para os arrays DP e tails - [Slice — Fatias e partition_point](/stdlib/slice/) — busca binária na biblioteca padrão - [Option — Valores opcionais](/stdlib/option/) — representação de predecessores nulos - [Subsequência Comum Mais Longa (LCS)](/algoritmos/longest-common-subsequence/) — outro problema clássico de subsequência - [Fibonacci com DP](/algoritmos/fibonacci-dp/) — introdução a programação dinâmica - [Problema da Mochila](/algoritmos/knapsack/) — outro clássico de DP com reconstrução