Problema da subsequência densa

Problema retirado do segundo teste do professor Carlos.

2) Considere uma sequência de números A=(a1,a2,…,an). Uma subseguencia S de A é dita densa se para todo elemento de ai existe j tal que:

  • aj está em S;
  • |i-j| <= 1.

Nota: informalmente, uma subsequencia S é densa em A se qualquer elemento ai de A ou está em S ou possui um vizinho em S.

Exemplo: A = <-1,9,-14,3,27,-19,35>

Neste caso (-1,9,27,35) e (9,3,-19) são subsequências densas de A, mas (9,-19,35) não é.

Os custos das subsequencias densas acinma são 70 e -7, respectivamente, e o custa da sequência não densa é de -45.

A subsequência ótima para este problema é (-1,-14,-19) .

Deixe um comentário »

RSS feed for comments on this post. TrackBack URI

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

Blog no WordPress.com.
Entries e comentários feeds.

%d blogueiros gostam disto: