Al doilea termen este de forma $A{~i-1,k~} - S{~k~}$ (termen independent de {$j$}) + {$S{~j~}$}. Astfel din linia $i-1$ a matricii de dinamica pentru fiecare $j$ ne trebuie valoarea maxima $A{~i-1,k~}-S{~k~}$ cu {$k<j$}. O prima idee ar fi ca pe masura ce construim linia i sa inseram elementele din linia $i-1$ intr-un max-heap astfel reducand complexitatea la {$O(N*lgN*K)$}.

Cei care au rezolvat probleme precum "secventa":http://www.infoarena.ro/task/secventa de pe info-arena, "trans":http://www.infoarena.ro/task/trans de la barajul de la ONI 2004 sau divide de la USACO Ianuarie 2005 vor realiza imediat ca putem reduce complexitatea la $O(N*K)$ folosind structura necesara in rezolvarea acelor probleme si anume o coada (in literatura de specialitate se intalneste ca "deque with heap order"). Aceasta structura a mai fost tratata si in solutiilor problemelor prezentate mai sus, deci nu voi intra in detalii. Este evident ca un algoritm de complexitate $O(N*K)$ se incadreaza in timp, dar mai apare in calcul faptul ca sirul este circular. Un algoritm $O(N*K)$ care nu trateaza acest lucru ia $40$ de puncte. O prima idee ar fi sa aplicam acelasi algoritm pe fiecare permutare circulara dar se ridica complexitatea iar la {$O(N^2^*K)$}. Aceasta abordare ar trebui sa obtina intre $50$ si $60$ de puncte. Putem trata circularitatea sirului tot in $O(N*K)$ incercand sa obtinem o secventa care contine elemente $N$ si {$1$}. Putem realiza acest lucru astfel:

Cei care au rezolvat probleme precum "secventa":problema/secventa de pe infoarena, "trans":problema/trans de la barajul de la ONI 2004 sau divide de la USACO Ianuarie 2005 vor realiza imediat ca putem reduce complexitatea la $O(N*K)$ folosind structura necesara in rezolvarea acelor probleme si anume o coada (in literatura de specialitate se intalneste ca "deque with heap order"). Aceasta structura a mai fost tratata si in solutiilor problemelor prezentate mai sus, deci nu voi intra in detalii. Este evident ca un algoritm de complexitate $O(N*K)$ se incadreaza in timp, dar mai apare in calcul faptul ca sirul este circular. Un algoritm $O(N*K)$ care nu trateaza acest lucru ia $40$ de puncte. O prima idee ar fi sa aplicam acelasi algoritm pe fiecare permutare circulara dar se ridica complexitatea iar la {$O(N^2^*K)$}. Aceasta abordare ar trebui sa obtina intre $50$ si $60$ de puncte. Putem trata circularitatea sirului tot in $O(N*K)$ incercand sa obtinem o secventa care contine elemente $N$ si {$1$}. Putem realiza acest lucru astfel:

* dupa ce realizam prima data dinamica, reinitializam linia $1$ astfel $A{~1,i~} = S{~i~}$
* aplicam din nou dinamica -> de data aceasta algoritmul va fi obligat sa intoarca rezultate care contin neaparat elementul $1$ intr-o secventa din cauza initializarii