O rezolvare in <tex>O(N*M^3^)</tex> este destul de la indemana. Parcurgem liniile de la 1 la N. Presupuem dinamica calculata pentru liniile < i. Atunci, la linia i, fixam fiecare subsecventa de coloane (j,k) j &le; k si actualizam in felul urmator:

* Fie @s(i,j,k) = dp[i][j] + dp[i][j+1] + ... + dp[i][k]@
* Fie @mv(i,j,k) = max(dp[i][j], dp[i][j+1],..., dp[i][k])@

* Definim @s(i,j,k) = dp[i][j] + dp[i][j+1] + ... + dp[i][k]@
* Definim @mv(i,j,k) = max(dp[i][j], dp[i][j+1],..., dp[i][k])@

* Atunci actualizam dp[i][h] = max(dp[i][h], s(i,j,k) + mv(i-1,j,k)) oricare h cu j ≤ h ≤ k
Calcularea lui s, mv precum si actualizarea se pot face parcurgand de la j la k, complexitatea finala fiind cea mentionata mai sus.