Autor da análise: cesargm
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2533
Resumo
É um problema de LIS (Longest Increasing Subsequence) simples.
Solução
Basta manter um vetor que guarda, na posição i, o menor elemento encontrado tal que existe uma subsequência crescente de tamanho i+1 terminando com ele.
O vetor começa com o primeiro elemento da sequência na posição 0. Percorremos o resto da sequência em ordem. Para cada elemento lido, encontramos no vetor a maior posição com valor menor que o elemento atual. O elemento é então guardado na posição seguinte a essa. (Como o vetor guarda elementos em ordem crescente é possível fazer uma busca binária - embora não seja necessário neste caso)
A resposta é o número de elementos do vetor.
Exemplo:
Sequência: 1 7 3 5 9 4 8
1 -> 1 / / / / / /
7 -> 1 7 / / / / /
3 -> 1 3 / / / / /
5 -> 1 3 5 / / / /
9 -> 1 3 5 9 / / /
4 -> 1 3 4 9 / / /
8 -> 1 3 4 8 / / /
Resposta: 4
Problema semelhante: Bridging signals [wiki | PKU]
Discuta o problema