Maior subsequência crescente

Seja uma array com $n$ números: $a[0 \dots n-1]$. A tarefa é encontrar a subsequência mais longa e estritamente crescente em $a$.

Formalmente, procuramos a sequência mais longa de índices $i_1, \dots i_k$ de modo que $$i_1 < i_2 < \dots < i_k,\\ a[i_1] < a[i_2] < \dots < a[i_k]$$

Neste artigo, discutimos vários algoritmos para resolver esta tarefa. Também discutiremos alguns outros problemas, que podem ser reduzidos a esse problema.

Solução em $O(n^2)$ com programação dinâmica

A programação dinâmica (Dynamic programming - dp) é uma técnica muito geral que permite resolver uma enorme classe de problemas. Aqui aplicamos a técnica para nossa tarefa específica.

Primeiro, procuraremos apenas o tamanho da subsequência crescente mais longa e então aprenderemos a como restaurar a própria subsequência.

Encontrando o tamanho

Para realizar essa tarefa, definimos uma array $d[0 \dots n-1]$, onde $d[i]$ é o comprimento da subsequência crescente mais longa que termina no elemento de índice $i$. Computaremos essa array gradualmente: primeiro $d[0]$, então $d[1]$, e assim por diante. Depois que essa array é calculada, a resposta para o problema será o valor máximo na array $d[]$.

Então deixe o índice atual ser $i$. Ou seja, queremos calcular o valor $d[i]$ e todos os valores anteriores $d[0], \dots, d[i-1]$ já são conhecidos. Assim, existem duas opções:

Se combinarmos esses dois casos, obteremos a resposta final para $d[i]$:

$$d[i] = \max\left(1, \max_{\substack{j = 0 \dots i-1 \\ a[j] < a[i]}} \left(d[j] + 1\right)\right)$$

Implementação

Aqui está uma implementação do algoritmo descrito acima, que calcula o comprimento da subsequência crescente mais longa.

int lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i])
                d[i] = max(d[i], d[j] + 1);
        }
    }

    int ans = d[0];
    for (int i = 1; i < n; i++) {
        ans = max(ans, d[i]);
    }
    return ans;
}

Restaurando a subsequência

Até agora, aprendemos apenas como encontrar o comprimento da subsequência, mas não como encontrar a própria subsequência.

Para poder restaurar a subsequência, geramos uma array auxiliar adicional $p[0 \dots n-1]$ que calcularemos junto com a array $d[]$. $p[i]$ será o índice $j$ do segundo último elemento na subsequência crescente mais longa que termina em $i$. Em outras palavras, o índice $p[i]$ é o mesmo índice $j$ no qual o valor mais alto $d[i]$ foi obtido. Essa array auxiliar $p[]$ aponta em certo sentido para os ancestrais.

Então, para derivar a subsequência, apenas começamos no índice $i$ com o máximo $d[i]$, e seguimos os ancestrais até deduzirmos toda a subsequência, ou seja, até atingirmos o elemento com $d[i] = 1$.

Implementação da restauração

Vamos mudar um pouco o código das seções anteriores. Vamos calcular a array $p[]$ juntamente com $d[]$, e depois calcularemos a subsequência.

Por conveniência, designamos originalmente os ancestrais com $p[i] = -1$. Para elementos com $d[i] = 1$, o valor dos ancestrais permanecerá $-1$, o que será um pouco mais conveniente para restaurar a subsequência.

vector<int> lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d(n, 1), p(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && d[i] < d[j] + 1) {
                d[i] = d[j] + 1;
                p[i] = j;
            }
        }
    }

    int ans = d[0], pos = 0;
    for (int i = 1; i < n; i++) {
        if (d[i] > ans) {
            ans = d[i];
            pos = i;
        }
    }

    vector<int> subseq;
    while (pos != -1) {
        subseq.push_back(a[pos]);
        pos = p[pos];
    }
    reverse(subseq.begin(), subseq.end());
    return subseq;
}

Maneira alternativa de restaurar a subsequência

Também é possível restaurar a subsequência sem a array auxiliar $p[]$. Podemos simplesmente recalcular o valor atual de $d[i]$ e também ver como o máximo foi alcançado.

Esse método leva a um código um pouco mais longo, mas, em troca, economizamos um pouco de memória.

Solução em $O(n \log n)$ com programação dinâmica e binary search

Para obter uma solução mais rápida para o problema, construímos uma solução de programação dinâmica diferente que é executada em $O(n^2)$, e, posteriormente, melhoramos para $O(n \log n)$.

Usaremos a array de programação dinâmica $d[0 \dots n]$. Desta vez, $d[i]$ será o elemento no qual uma subsequência de comprimento $i$ termina. Se houver várias dessas sequências, pegamos a que termina no menor elemento.

Inicialmente assumimos $d[0] = -\infty$ e para todos os outros elementos $d[i] = \infty$.

Novamente, processaremos gradualmente os números, primeiro $a[0]$, então $a[1]$, etc, e em cada etapa manteremos a array $d[]$ para que ela esteja atualizada.

Depois de processar todos os elementos de $a[]$ o comprimento da subsequência desejada é o maior $l$, com $d[l] < \infty$.

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= n; j++) {
            if (d[j-1] < a[i] && a[i] < d[j])
                d[j] = a[i];
        }
    }

    int ans = 0;
    for (int i = 0; i <= n; i++) {
        if (d[i] < INF)
            ans = i;
    }
    return ans;
}

Agora fazemos duas observações importantes.

A array $d$ sempre será ordenada: $d[i-1] \le d[i]$, para todo $i = 1 \dots n$. E também o elemento $a[i]$ somente atualizará no máximo um valor $d[j]$.

Assim, podemos encontrar esse elemento na array $d[]$ usando binary search em $O(\log n)$. De fato, estamos simplesmente procurando na array $d[]$ pelo primeiro número estritamente maior que $a[i]$, e tentamos atualizar esse elemento da mesma maneira que na implementação acima.

Implementação

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        int j = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
        if (d[j-1] < a[i] && a[i] < d[j])
            d[j] = a[i];
    }

    int ans = 0;
    for (int i = 0; i <= n; i++) {
        if (d[i] < INF)
            ans = i;
    }
    return ans;
}

Restaurando a subsequência

Também é possível restaurar a subsequência usando essa abordagem. Desta vez, temos que manter duas arrays auxiliares. Uma que nos diz os índices dos elementos em $d[]$. E, novamente, temos que criar uma array de "ancestrais" $p[]$. $p[i]$ será o índice do elemento anterior para a subsequência ideal que termina no elemento $i$.

É fácil manter essas duas arrays no curso da iteração sobre a array $a[]$ juntamente com o computação de $d[]$. E, no final, não é difícil restaurar a subsequência desejada usando essas arrays.

Solução em $O(n \log n)$ com estruturas de dados

Em vez do método acima, para calcular a subsequência crescente mais longa em $O(n \log n)$ também podemos resolver o problema de uma maneira diferente: usando algumas estruturas de dados simples.

Vamos voltar ao primeiro método. Lembre-se de que $d[i]$ é o valor $d[j] + 1$, com $j < i$ e $a[j] < a[i]$.

Portanto, se definirmos uma array adicional $t[]$ de modo que $$t[a[i]] = d[i],$$ então, o problema de calcular o valor $d[i]$ será equivalente a encontrar o valor máximo em um prefixo da array $t[]$: $$d[i] = \max\left(t[0 \dots a[i] - 1] + 1\right)$$

O problema de encontrar o máximo de um prefixo de uma array, é um problema padrão que pode ser resolvido por muitas estruturas de dados diferentes. Por exemplo, podemos usar uma árvore segmentária ou a árvore de Fenwick.

Este método tem obviamente algumas deficiências: em termos de extensão e complexidade da implementação, essa abordagem será pior que o método que utiliza a busca binária. Além disso, se os números de entrada $a[i]$ forem especialmente grandes, teremos que usar alguns truques, como comprimir os números (ou seja, renumerá-los de $0$ até $n-1$), ou usar uma árvore segmentária implícita (gerar apenas os segmentos da árvore que são importantes). Caso contrário, o consumo de memória será muito alto.

Por outro lado, esse método também tem algumas vantagens: com esse método, você não precisa pensar em nenhuma propriedade complicada na solução de programação dinâmica. E essa abordagem nos permite generalizar o problema.

Tarefas relacionadas

Aqui estão vários problemas que estão intimamente relacionados ao problema de encontrar a subsequência crescente mais longa.

Subseqüência não decrescente mais longa

Na verdade, é quase o mesmo problema. Somente agora é permitido usar números idênticos na subsequência.

A solução é essencialmente também quase a mesma. Nós apenas temos que alterar os sinais de desigualdade e fazer uma pequena modificação na busca binária.

Número de subsequências crescentes mais longas

Podemos usar o primeiro método discutido, a versão em $O(n^2)$ ou a versão usando estruturas de dados. Apenas precisamos armazenar adicionalmente de quantas maneiras podemos obter subsequências crescentes mais longas, terminando nos valores $d[i]$.

O número de maneiras de formar as subsequências crescentes mais longas que terminam em $a[i]$ é a soma de todas as maneiras para todas as subsequências crescentes mais longas que terminam em $j$, onde $d[j]$ é máximo. Podem existir múltiplos desses $j$'s, portanto, precisamos somar todos eles.

Usando uma árvore de segmentos, essa abordagem também pode ser implementada em $O(n \log n)$.

Não é possível usar a abordagem de busca binária para esta tarefa.

Menor número de subsequências não crescentes que cobrem uma sequência

Para uma array com $n$ números $a[0 \dots n - 1]$ temos que colorir os números com o menor número de cores, para que cada cor forme uma subsequência não crescente(se isso fizer sentido).

Para resolver isso, notamos que o número mínimo de cores necessárias é igual ao comprimento da subsequência crescente mais longa.

Prova: Precisamos provar a dualidade desses dois problemas.

Vamos denotar por $x$ o comprimento da subsequência crescente mais longa e por $y$ o menor número de subsequências não crescentes que formam uma cobertura. Precisamos provar que $x = y$.

É claro que $y < x$ não é possível, porque se tivermos $x$ elementos estritamente crescentes, então dois elementos não poderão fazer parte da mesma subsequência não crescente. Portanto, temos $y \ge x$.

Agora mostramos que $y > x$ não é possível por contradição. Suponha que $y > x$. Em seguida, consideramos qualquer conjunto ideal de $y$ subsequências sem aumento. Transformamos isso em um conjunto da seguinte maneira: desde que existam duas subsequências, de modo que a primeira comece antes da segunda e a primeira sequência inicie com um número maior ou igual ao segundo, então deslocamos esse número inicial e anexamos ele ao início da segunda. Após um número finito de etapas, temos $y$ subsequências, e seus números iniciais formarão uma subsequência crescente de comprimento $y$. Como assumimos que $y > x$ chegamos a uma contradição.

Assim, segue-se que $y = x$.

Restaurando as sequências: A partição desejada da sequência em subsequências pode ser feita com um método guloso(greedy). Ou seja, vá da esquerda para a direita e atribua o número atual ou a subsequência que termina com o número mínimo que é maior ou igual ao atual.

Problemas