Damos um array com números $n$: $a$.A tarefa é encontrar a subseguência mais longa, estritamente crescente, em $a$.

Formalmente procuramos a sequência mais longa de índices $i_1, pontos i_k$ tal que $$i_1 < i_2 < pontos < i_k,\a < a < pontos < a$

Neste artigo discutiremos vários algoritmos para resolver esta tarefa.

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

Programação dinâmica é uma técnica muito geral que permite resolver uma grande classe de problemas, aqui aplicamos a técnica para a nossa tarefa específica.

Primeiro vamos procurar apenas o comprimento da subsequence de maior aumento, e só mais tarde aprender a restaurar a subsequence em si.

Localizar o comprimento

Para realizar esta tarefa, definimos um array $d$, onde $d$ é o comprimento da subsequence de maior aumento que termina no elemento no índice $i$.Vamos calcular este array gradualmente: primeiro $d$, depois $d$, e assim por diante. Após este array ser calculado, a resposta ao problema será o valor máximo no array $d$.

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

• $d = 1$: a subsequência necessária consiste apenas no elemento $a$.
• $d > 1$: então na subsequence requerida é outro número antes do número $a$. Vamos focar nesse número:pode ser qualquer elemento $a$ com $j = 0 \dots i-1$ e $a < a$.Desta forma, podemos calcular $d$ usando a seguinte fórmula: Se fixarmos o índice $j$, que o maior aumento subsequence terminando nos dois elementos $a$ e $a$ tem o comprimento $d + 1$. Todos estes valores $d$ já são conhecidos, então podemos calcular diretamente $d$ com:$$$d = \max_{\substack{j = 0 \dots i-1 \ a < a}}} \esquerda(d + 1) $$

Se combinarmos estes dois casos obtemos a resposta final por $d$:

$$$d = {\i1, {\i}max_{\i1}esquerda(1, {\i}max_{\i}{j = 0 pontos i-1 {\i} a < a}} \esquerda(d + 1\ direita)\ direita)$$

Implantação

Aqui está uma implementação do algoritmo descrito acima, que calcula o comprimento da subsequence o mais longo aumento.

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 < a) d = max(d, d + 1); } } int ans = d; for (int i = 1; i < n; i++) { ans = max(ans, d); } return ans;}

Restaurar a subsequence

Até agora só aprendemos como encontrar o comprimento da subsequence, mas não como encontrar a subsequence em si.

Para ser capaz de restaurar a subsequence nós geramos um array auxiliar adicional $p$ que vamos calcular ao lado do array $d$.$p$ será o índice $j$ do segundo último elemento na subsequence mais longa aumentando terminando em $i$.Em outras palavras, o índice $p$ é o mesmo índice $j$ no qual o maior valor $d$ foi obtido.Esta matriz auxiliar $p$ pontos em algum sentido para os antepassados.

Então para derivar a subsequence, nós apenas começamos no índice $i$ com o máximo $d$, e seguir os antepassados até que deduzimos toda a subsequence, ou seja, até chegarmos ao elemento com $d = 1$.

Implementação de restauração

Nós vamos mudar o código das seções anteriores um pouco.Vamos calcular a matriz $p$ ao lado de $d$, e depois calcular a subsequence.

Por conveniência, originalmente atribuímos os antepassados com $p = -1$. Para elementos com $d = 1$, o valor dos antepassados permanecerá $-1$, que será ligeiramente mais conveniente para restaurar a subsequence.

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 < a && d < d + 1) { d = d + 1; p = j; } } } int ans = d, pos = 0; for (int i = 1; i < n; i++) { if (d > ans) { ans = d; pos = i; } } vector<int> subseq; while (pos != -1) { subseq.push_back(a); pos = p; } reverse(subseq.begin(), subseq.end()); return subseq;}

Alternativa forma de restaurar a subsequence

Também é possível restaurar a subsequence sem a matriz auxiliar $p$.Podemos simplesmente recalcular o valor atual de $d$ e também ver como o máximo foi alcançado.

Este método leva a um código um pouco mais longo, mas em troca nós salvamos alguma memória.

Solução em $O(n \log n)$ com programação dinâmica e busca binária

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

Usaremos o array de programação dinâmica $d$.Desta vez $d$ será o elemento em que uma subseqüência de comprimento $i$ termina. Se existem múltiplas sequências deste tipo, então tomamos a que termina no menor elemento.

Inicialmente assumimos $d = -\i$ e para todos os outros elementos $d = \i$.

Vamos novamente processar gradualmente os números, primeiro $a$, depois $a$, etc, e em cada etapa manter o array $d$ para que ele esteja atualizado.

Após processar todos os elementos de $a$ o comprimento da subsequence desejada é o maior $l$ com $d < \i< \i

int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { for (int j = 1; j <= n; j++) { if (d < a && a < d) d = a; } } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

Agora fazemos duas observações importantes.

O array $d$ será sempre ordenado: $d \le d$ para todos os $i = 1 \dots n$.E também o elemento $a$ só actualizará no máximo um valor $d$.

Assim podemos encontrar este elemento no array $d$ usando a pesquisa binária em $O(\log n)$.Na verdade, estamos simplesmente procurando no array $d$ para o primeiro número que é estritamente maior que $a$, e tentamos atualizar este elemento da mesma forma que a 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 = -INF; for (int i = 0; i < n; i++) { int j = upper_bound(d.begin(), d.end(), a) - d.begin(); if (d < a && a < d) d = a; } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

Restaurar a subsequence

Também é possível restaurar a subsequence usando esta abordagem.Desta vez temos de manter dois arrays auxiliares. Um que nos diz o índice dos elementos em $d$. E novamente temos de criar um array de “ancestrais” $p$.$p$ será o índice do elemento anterior para a subsequence ótima terminando no elemento $i$.

É fácil manter estes dois arrays no curso da iteração sobre o array $a$, juntamente com os cálculos de $d$.E no final não é difícil restaurar a subsequence desejado usando estes arrays.

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

Em vez do método acima para calcular a subsequence mais longo aumento em $O(n \log n)$ também podemos resolver o problema de uma maneira diferente: usando algumas estruturas de dados simples.

Assim se definirmos um array adicional $t$ tal que $$$t] = d,$$$então o problema de calcular o valor $d$ é equivalente a encontrar o valor máximo em um prefixo do array $t$:$$d = \max\esquerda(t – 1] + 1\direita)$$

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

Este método tem obviamente algumas falhas:em termos de comprimento e complexidade da implementação esta abordagem será pior do que o método que usa a busca binária. Além disso, se os números de entrada $a$ forem especialmente grandes, então teríamos que usar alguns truques, como comprimir os números (ou seja, renumerá-los de $0$ para $n-1$), ou usar uma árvore de Segmentos implícita (apenas gerar os ramos da árvore que são importantes).Caso contrário o consumo de memória será muito alto.

Por outro lado este método também tem algumas vantagens:com este método você não precisa pensar em nenhuma propriedade complicada na solução de programação dinâmica.E esta abordagem nos permite generalizar o problema muito facilmente (veja abaixo).

Tarefas relacionadas

Aqui estão vários problemas que estão intimamente relacionados com o problema de encontrar a subsequência de maior aumento.

A solução é essencialmente também quase o mesmo.Temos apenas que mudar os sinais de desigualdade, e fazer uma ligeira modificação na pesquisa binária.

Número de sub-segundas de maior aumento

Podemos usar o primeiro método discutido, seja a versão $O(n^2)$ ou a versão usando estruturas de dados.Nós só temos que armazenar adicionalmente em quantas maneiras podemos obter subsequences mais longo aumento terminando nos valores $d$.

O número de maneiras de formar uma subsequences mais longo aumento terminando em $a$ é a soma de todas as maneiras para todas as subsequences mais longo aumento terminando em $j$ onde $d$ é o máximo.Pode haver múltiplos tais $j$, então precisamos somar todos eles.

Usando uma árvore de segmentos esta 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.

Mais pequeno número de subseqüências não crescentes cobrindo uma seqüência

Para um dado array com números $n$ $a$ temos que colorir os números no menor número de cores, de modo que cada cor forma uma subseqüência não crescente.

Para resolver isso, notamos que o número mínimo de cores necessárias é igual ao comprimento da subsequence de maior aumento.

Prova:Temos de provar a dualidade destes dois problemas.

Denotar por $x$ o comprimento da subsequence o mais longo aumento e por $y$ o menor número de subsequences não-crescente que formam uma cobertura. Precisamos provar que $x = y$.

É claro que $y < x$ não é possível, porque se temos $x$ estritamente aumentando elementos, do que não dois podem fazer parte da mesma subsequence não-crescente.Portanto, temos $y \ge x$.

Mostramos agora que $y > x$ não é possível por contradição. Suponha que $y > x$.Então nós consideramos qualquer conjunto óptimo de $y$ subsequences não-increasing.Nós transformamos isso no conjunto da seguinte maneira: desde que haja duas dessas sub-segundas, de modo que a primeira começa antes da segunda sub-segunda, e a primeira seqüência começa com um número maior ou igual ao segundo, então nós desenganchar este número inicial e anexá-lo ao início da segunda.Depois de um número finito de passos que temos $y$ subsequences, e seus números de partida irá formar uma subsequence crescente de comprimento $y$.Desde que assumimos que $y > x$ chegamos a uma contradição.

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

Restaurar as sequências:A partição desejada da sequência em subsequences pode ser feito gananciosamente.Isto é, ir da esquerda para a direita e atribuir o número atual ou que subsequence terminando com o número mínimo que é maior ou igual ao número atual.

Problemas de prática

• Topcoder – IntegerSequence
• Topcoder – AutoMarket
• Codeforces – Tourist
• Codeforces – LCIS
• SPOJ – SUPPER
• Topcoder – BridgeArrangement
• ACMSGURU – “Nordeste”