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) .

Sem comentários ainda »

Feed RSS dos comentários deste post URI do TrackBack

Deixe um comentário

XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <pre> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Blog no WordPress.com. | Theme: Pool by Borja Fernandez.
Entries and comments feeds.