PKU 2533 - Longest Ordered Subsequence

Autor da análise: cesargmcesargm

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]

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
lis
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License