Cu aceste observatii, putem folosi un deque in cadrul algoritmului nostru, care contine functiile 'aparute' pana la fiecare pas p. Functiile sunt sortate dupa valoarea lor la pasul p, precum si dupa momentul la care urmeaza sa devina functii cu valoare minima. La fiecare pas p se introduce in deque o functie noua, functia f{~i,p~}. Aceasta va elimina toate functiile care au la pasul p o valoare mai mare decat a ei, precum si acele functii pe care le-ar depasi intr-un punct x mai mic decat momentul minim posibil la care acestea ar putea deveni functii cu valoare minima (pentru ca, astfel, acestea nu vor mai deveni niciodata functii cu valoare minima). De asemenea, la fiecare pas p se elimina din partea din fata a deque-ului functiile pentru care functia de dupa ea are punctul in care devine minima mai mic sau egal cu d[p].

Pentru a calcula punctul x{~j,j{~1~}~} in care o functie f{~i,j{~1~}~} depaseste o functie f{~i,j~} (j<j{~1~}), trebuie sa calculam urmatoarele valori. Sa presupunem ca ne aflam la pasul p=j{~1~}. Vom calcula dC = f{~i,j{~1~}~}(d[j{~1~}]) - fi,j(d[j{~1~}]). Vom observa acum ca functiile f{~i,j~} au fost definite pe un interval de distante, deoarece, intre doua distante corespunzatoare a doua benzinarii consecutive, ele se comporta ca niste drepte. La pasul p=j{~1~}, dreapta corespunzatoare functiei f{~i,j~} are o panta egala cu dP=(c[j] + c[j+1] + .. + c[j1-1]), iar dreapta corespunzatoare functiei f{~i,j{~1~}~} are panta 0. In fiecare punct mai mare decat punctul d[j{~1~}], diferenta dintre pantele dreptelor corespunzatoare celor 2 functii in punctul respectiv va ramane constanta si egala cu dP. Se observa
usor ca acest lucru este adevarat, pentru ca pantele dreptelor asociate cresc cu aceeasi valoare in fiecare punct in care se afla localizata o benzinarie. Prin urmare, punctul x in care functia f{~i,j{~1~}~} depaseste functia f{~i,j~} este x=d[j{~1~}] + dC/dP.

Pentru a calcula punctul x{~j,j{~1~}~} in care o functie f{~i,j{~1~}~} depaseste o functie f{~i,j~} (j<j{~1~}), trebuie sa calculam urmatoarele valori. Sa presupunem ca ne aflam la pasul p=j{~1~}. Vom calcula dC = f{~i,j{~1~}~}(d[j{~1~}]) - fi,j(d[j{~1~}]). Vom observa acum ca functiile f{~i,j~} au fost definite pe un interval de distante, deoarece, intre doua distante corespunzatoare a doua benzinarii consecutive, ele se comporta ca niste drepte. La pasul p=j{~1~}, dreapta corespunzatoare functiei f{~i,j~} are o panta egala cu dP=(c[j] + c[j+1] + .. + c[j1-1]), iar dreapta corespunzatoare functiei f{~i,j{~1~}~} are panta 0. In fiecare punct mai mare decat punctul d[j{~1~}], diferenta dintre pantele dreptelor corespunzatoare celor 2 functii in punctul respectiv va ramane constanta si egala cu dP. Se observa usor ca acest lucru este adevarat, pentru ca pantele dreptelor asociate cresc cu aceeasi valoare in fiecare punct in care se afla localizata o benzinarie. Prin urmare, punctul x in care functia f{~i,j{~1~}~} depaseste functia f{~i,j~} este x=d[j{~1~}] + dC/dP.

h3. {*Calculul valorilor cmin[ i ][ j ][ 1 ]*}