Analiza

Da bismo odredili pronašli optimalno rešenje, isprobaćemo svih ~N + 1~ mogućih izbora za broj prevrnutih kutija ~K~ (gde ~0 \leq K \leq N~). Neophodno je da za svako ~K~ odredimo najveće čekanje, i onda je ukupno rešenje minimum tih vrednosti.

Najveće čekanje ćemo odrediti tako što za svaku raketu izračunamo koliko će čekati i uzmemo maksimum tih vrednosti. Ovo možemo da uradimo u ~O(N^3)~ -- nakon što "okrenemo" prvih ~K~ elemenata niza ~T~, za svaku kutiju znamo da će se "osloboditi" kada sve kutije iznad nje budu odnesene, tj. da će ~i~-ta kutija biti na vrhu gomile u trenutku ~max(T_j : j < i)~ i samim tim čekati ~min(0, T_i - max(T_j : j < i))~ (na kutiju ne može da se čeka negativno dugo). Računanje ovih maksimuma u linearnom vremenu (prolaženjem kroz ~T~) daje ukupno kvadratnu složenost za određivanje čekanja svih raketa (za fiksno ~K~).

Ako za računanje gore opisanih maksimuma iskoristimo već izračunatu vrednost za prethodni element niza (posmatramo maksimum prethodne vrednosti i trenutnog elementa ~T_{i-1}~), možemo odrediti sva čekanja u jednom prolazu kroz niz, tako da je ukupna složenost ~O(N^2)~ (~O(N)~ za svako ~K~).

Za fiksno ~K~, kutije možemo podeliti u dve grupe -- one koje su u prevrnutom delu gomile i kutije ispod prevrnutog dela. Označimo maksimalna čekanja u ove dve grupe sa ~U_K~ i ~D_K~ redom.

Za fiksno ~K~, najveće čekanje u okrenutom delu gomile je uzrokovano ili jednom od kutija iz prvih ~K-1~ (u originalnom nizu) koja čeka na ~K~-tu (sada gornju), ili čekanjem jedne od prvih ~K-1~ na drugu iz istog skupa. Prva vredmost se može odrediti kao ~min(0, T_K - max(T_i : i < K))~, a druga je jednaka ~U_{K-1}~, tako da se ceo niz ~U~ može izračunati u ~O(N)~ (opet, neophodno je da pamtimo maksimume svih prefiksa i računamo ih kao u prethodnom delu).

Pošto na kutije koje nisu okrenute ne utiče raspored kutija iznad njih, za vremena čekanja koja utiču na ~D_K~ možemo uzeti vremena za ~K=0~ (koja računamo u ~O(N)~ na ranije opisan način), gde je ~D_K~ maksimum sufiksa ovog niza. Kao i za čekanja, ovo možemo odrediti u jednom prolazu (unazad), na osnovu već izračunatog ~D_{K+1}~.

Nakon što u linearnom vremenu izračunamo nizove ~U~ i ~D~, konačno rešenje je najmanja vrednost ~max(U_i, D_i)~, tako da je ukupna složenost algoritma ~O(N)~.