[Programmazione dinamica] K-sottosequenze a somma massima

[kily2001]

ciao a tutti, dovrei eseguire questo esercizio con la programmazione dinamica:

Si consideri una sequenza di interi X. La cancellazione da X di
un certo numero di elementi determina una sottosequenza. Una k-sottosequenza di X è una
sottosequenza di X in cui compaiono al più k elementi consecutivi di X.
Data una sequenza X di n interi ed un intero k, con k <= n vogliamo trovare una k-sottosequenza
di X la somma dei cui elementi sia massima.
Ad esempio, per X = (9, 8, 1, 9, 2, 9, 8, 2, 1, 8, 8, 1) e k = 3 la 3-sottosequenza a somma massima è
(9, 8, 9, 9, 8, 8, 8, 1) e vale 60.

Visto che il costo deve essere O(k*n) avevo pensato di usare una matrice T di grandezza k*n, dove nel generico T[i,j] trovo il massimo valore per la j-sottosequenza di X1...Xi (ad esempio considerando i=4 e j=2 avrò la 2-sottosequenza 9-9-9 che vale 27).

Qualcuno mi aiuta ad impostare la ricorrenza?

Grazie mille