Carnati
Prima observatie pe care o facem este faptul ca pretul fixat de Gigel va fi unul dintre preturile clientilor sai. Odata ce avem fixat un pret X putem sa construim o dinamica Ai profitul maxim daca magazinul este deschis in momentul in care trece clinetul i (clientii vor fi sortati crescator dupa timpul la care trec). Relatia de recurenta se observa usor Ai= max(Ai-1-(Ti-Ti-1)*C+G,G-C), unde G este X pentru X ≤ Pi sau 0 in caz contrar. De fapt, avand fixat X si construind vectorul H2*i=G-C, H2*i+1=-(Ti-Ti-1)*C problema se reduce la determinarea subsecventei de suma maxima.
Complexitatea de rezolvare pentru X fixat este O(N), deci in final algoritumul va fi O(N2)
