La prima vedere, problema pare abordabila cu programare dinamica. O simpla rezolvare care nu tine cont de faptul ca sirul este circular este urmatoarea: $A{~i,j~}$ = productivitatea maxima pentru a face $i$ strangeri din primele $j$ sectoare; evident raspunsul va fi {$A(K, N)$}. Relatia de recurenta:

* $A{~i,j~}$ = $max (A{~i,j-1~}, A{~i-1,k~} + suma P{~k~},P{~k+1~}..P{~j~})$ pentru fiecare {$k<j$}, iar $P$ reprezinta vectorul de productivitati.

* $A{~i,j~}$ = $max (A{~i,j-1~}, A{~i-1,k~} + suma (P{~k~},P{~k+1~}..P{~j~})$ pentru fiecare {$k<j$}, iar $P$ reprezinta vectorul de productivitati.

O astfel de implementare are complexitate $O(N^2^*K)$ si nu se va incadra in timp. Fie {$S{~i~} = P{~1~}+P{~2~}+...P{~i~}$}, atunci putem rescrie relatia de recurenta astfel:

O astfel de implementare are complexitate $O(N^2^*K)$ si nu se va incadra in timp. Fie {$S{~i~} = P{~1~}+P{~2~}+...+P{~i~}$}, atunci putem rescrie relatia de recurenta astfel:

* {$A{~i,j~} = max(A{~i,j-1~}, A{~i-1,k~} + S{~j~} - S{~k~})$}, pentru fiecare $k<j$

h3. Poligon
Problema cere sa determinam cate puncte din cele $M$ sunt in interiorul poligonului. O abordare imediata a acestei probleme ar fi sa determinam pentru fiecare punct in $O(N)$ daca este sau nu in interiorul poligonului. Exista mai multe moduri de a rezolva acest lucru. Un mod ar fi sa ducem o semidreapta pornind din punctul nostru si sa vedem de cate ori intersecteaza laturile poligonului: daca intersecteaza poligonul de un numar par de ori atunci inseamna ca punctul este in exterior, iar daca ea intersecteaza de un numar impar de ori laturile poligonului inseamna ca punctul este in interior. O alta modalitate: calculam suma unghiurilor pe care le fac extremele laturilor cu punctul nostru (unghiurile sunt luate pozitive sau negative dupa cum cele $3$ puncte ce formeaza unghiul sunt in sens trigonometric sau orar), daca suma unghiurilor pentru toate laturile e $0$ atunci punctul e in exteriorul poligonului, iar daca suma unghiurilor e $2*Pi$ atunci punctul e in interiorul poligonului, pentru mai multe detalii puteti

sa va uitati pe urmatoarele pagini:
 
"[1]":http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
"[2]":http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

sa va uitati pe urmatoarele pagini: "[1]":http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html "[2]":http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Dimensiunile datelor de intrare ne sugereaza ca trebuie sa acceleram determinarea pozitiei punctelor fata de poligon. Daca poligonul ar fi convex, este usor sa facem acest test in {$O(log N)$}: consideram un varf al poligonului si semidrepte ce pleaca din el spre celelalte varfuri, cu cautare binara gasim in ce sector determinat de doua semidrepte intra punctul pentru care vrem sa determinam incluziunea in poligon, dupa ce gasim sectorul testul de incluziune se reduce la determinarea incluziunii intr-un triunghi. Aceasta metoda eleganta si simpla merge pentru poligon convex, dar pentru unul oarecare trebuie sa gasim o alta abordare.