Vrem sa coboram complexitatea la <tex>O(N*M^2^)</tex>. Valorile lui s si mv sunt usor de obtinut in <tex>O(M^2^)</tex> pe linie parcurgand subsecventele de coloane in modul corespunzator. Problema este cum actualizam ? Vom utiliza o dinamica auxiliara independenta de linii (adica una care se refera doar la o singura linie la un moment dat).

* pe linia i, @auxdp[j][k] = valoarea minima a lui dp[i][h] cu h intre j si k.@

* pe linia i, @auxdp[j][k] = valoarea maxima a lui dp[i][h] cu h intre j si k.@

Definitia ne ajuta mai putin sa intelegem functionalitatea acestei dinamici. Ce facem cu ea este ca atunci cand am calculat s(i,j,k) + mv(i-1,j,k) pentru o subsecventa (j,k) in loc sa facem un _for_ de la j la k, incarcam valoarea in @auxdp[j][k]@. Dupa ce am parcurs toate subsecventele de coloane, le parcurgem a doua oara, de data aceasta in ordinea inversa a lungimii si actualizam in felul urmator:
* auxdp[j+1][k] = max (auxdp[j+1][k], auxdp[j][k]) cu j < k