[Algoritmica]K-sottosequenze a somma massima

[Ext3rmin4tor]

Sto diventando scemo (se non lo sono già!) cercando di trovare una soluzione a questo problema:

Data una sequenza di interi positivi X di lunghezza n si dice K-sottosequenza una sottosequenza di X in cui compaiono al massimo k elementi consecutivi di X. Trovare la K-sottosequenza di somma massima in X.

Dovrebbe essere possibile risolverlo con un algoritmo di programmazione dinamica, solo che non riesco a capire come fare. Se qualcuno sa come aiutarmi verrà calorosamente ringraziato , basta solo lo pseudocodice non serve che sia implementato.

[apatriarca]

Supponiamo di conoscere la $k$-sottosequenza di somma massima dei primi $m \ge k$ elementi della sequenza. La $k$-sottosequenza di somma massima dei primi $m+1$ elementi della sequenza può essere o la stessa dei primi $m$ elementi o quella formata dagli ultimi $k$ elementi di questa sottosequenza.

Inizi quindi scegliendo la $k$-sottosequenza formata dai primi $k$ elementi della sequenza, ad ogni iterazione aggiungi un elemento nella sottosequenza da considerare e confronti la somma della $k$-sottosequenza con somma massima trovata con quella data dagli ultimi elementi della sottosequenza che stai considerando. Se quest'ultima è maggiore allora hai trovato una nuova $k$-sottosequenza con somma massima.

[Ext3rmin4tor]

Tu mi dici che ad ogni iterazione devo aggiungere un elemento alla sottosequenza, ma così facendo ad un certo punto violerei il vincolo dei k elementi consecutivi. Non so se ho capito male, magari se riesci scrivi lo pseudocodice.

[vict85]

Il metodo presentato da apatriarca consiste nel prendere la prima k-sequenza [0, k] e confrontarla con la seconda [1, k+1] e così via fino all'ultima.

Se con S(x) indico la somma degli elementi che vanno da v[x] a v[x+k], vale la seguente ugualianza:

S(x+1) = S(x) - v[x] + v[x+k+1]