CKTIS / C
Subsequência crescente mais longa (LIS)
Uma LIS é a subsequência estritamente crescente mais longa que preserva a ordem de entrada sem exigir que os elementos sejam adjacentes. O exemplo em C calcula o seu comprimento através de programação dinâmica, em O(n²) tempo e com O(n) espaço auxiliar.
Versão: C23; repository compiler flag, production runtime not attested
Sintaxe
dp[i] = max({1} union {dp[j] + 1 | 0 <= j < i and a[j] < a[i]}); LIS length = n == 0 ? 0 : max(dp)Uma longest increasing subsequence (LIS), ou subsequência crescente mais longa, seleciona elementos pela sua ordem original. É possível ignorar elementos; a seleção não tem de ser contígua. Para {3, 1, 2, 2, 4}, a subsequência {1, 2, 4} tem o comprimento máximo 3. Ordenar a entrada alteraria o problema, pois perder-se-ia a ordem original.
A distinção strictly increasing versus non-decreasing significa que uma subsequência estritamente crescente exige <, enquanto uma não decrescente permite <=. Valores iguais não prolongam uma LIS. Substituir a[j] < a[i] por a[j] <= a[i] produz um algoritmo para a subsequência não decrescente mais longa; para os dados do exemplo, o seu comprimento é 4.
Seja dp[i] o comprimento da melhor subsequência que termina exatamente em a[i]. Inicialize-o com 1. Para cada j < i que satisfaça a[j] < a[i], considere dp[j] + 1. Calcule os estados da esquerda para a direita e mantenha o resultado mais elevado. Os ciclos aninhados requerem O(n²) tempo e o array dp utiliza O(n) espaço auxiliar.
O exemplo devolve apenas o comprimento. Registar os índices dos predecessores é opcional: se a entrada não estiver vazia, é possível reconstruir uma LIS a partir de a e dp. Comece por selecionar a[i] num índice i em que dp[i] seja máximo. Percorra os índices para trás e selecione a[j] quando se verificarem j < i, a[j] < a[i] e dp[j] + 1 == dp[i]. Após cada seleção, atribua a i o valor de j. Pare quando dp[i] == 1 e inverta a ordem dos elementos selecionados.
Quem chama fornece arrays a e dp que não se sobrepõem e que contêm, cada um, pelo menos n elementos. Para n == 0, a função devolve 0 sem aceder a qualquer dos arrays, pelo que NULL é permitido. Não utiliza alocação dinâmica nem arrays de comprimento variável.
Exemplos
#include <stddef.h>
#include <stdio.h>
/* For n > 0, a and dp must each provide at least n elements.
Their storage must not overlap. For n == 0, both may be NULL. */
static size_t lis_length(const int *a, size_t n, size_t *dp)
{
size_t best = 0;
for (size_t i = 0; i < n; ++i) {
dp[i] = 1;
for (size_t j = 0; j < i; ++j) {
if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > best) {
best = dp[i];
}
}
return best;
}
int main(void)
{
const int a[] = {3, 1, 2, 2, 4};
size_t dp[sizeof a / sizeof a[0]];
printf("LIS length: %zu\n", lis_length(a, sizeof a / sizeof a[0], dp));
printf("Empty length: %zu\n", lis_length(NULL, 0, NULL));
return 0;
}
Resultado
LIS length: 3 Empty length: 0
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.