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