Se va calcula pentru fiecare sir *max[i] = suma maxima a unei subsecvente de lungime i* in O(N²).
Avand *max1* si *max2* (pentru cele doua siruri), in O(N x M) putem incerca toate lungimile *L1*, *L2* (1 <= L1 <= N, 1 <= L2 <= M) de secvente posibile pentru cele doua siruri iar cu formula de mai sus putem calcula suma maxima ce se poate obtine pentru lungimile respective. Vom salva si afisa valoarea maxima. Complexitatea finala este O(N² + M² + N x M)

h1(#MaxSubSum). 'B. Avioane2':problema/Avioane2

h1(#Avioane2). 'B. Avioane2':problema/Avioane2

?

Din zborurile care sunt date, se construieste un graf in care nodurile sunt perechi de forma <tex>(aeroport, timp)</tex>. Sunt suficiente numai perechile din zborurile initiale (cel mult <tex>2*M</tex> perechi, deci tot atatea noduri), plus inca o pereche <tex>(1, 0)</tex> (aeroportul 1, timpul 0) de la care se porneste.
 
Muchiile se leaga in felul urmator:
1. intre nodurile de forma <tex>(aeroport_d_e_c, timp_d_e_c)</tex> si <tex>(aeroport_a_t_e_r, timp_a_t_e_r)</tex> (intre care exista zbor) se leaga o muchie avand costul <tex>P</tex> corespunzator zborului. Se obtin <tex>M</tex> muchii de zbor;
2. intre nodurile corespunzatoare aceluiasi aeroport se leaga muchii cu cost <tex>0</tex> (costul de asteptare) de la nodul cu timp mai mic la nodul imediat urmator ca timp. De exemplu, daca pentru aeroportul <tex>5</tex> am zboruri (care ajung sau pleaca) la timpii <tex>1</tex>, <tex>10</tex>, <tex>15</tex>, <tex>21</tex>, se vor pune muchii intre perechile: <tex>(5, 1) - (5, 10)</tex>, <tex>(5, 10) - (5, 15)</tex>, <tex>(5, 15) - (5, 21)</tex>. Daca cei doi ajung in aeroportul 5 la timpul 10 si vor sa plece la timpul 21, drumul <tex>(5, 10) - (5, 15) - (5, 21)</tex> va corespunde asteptarii si va avea cost 0. Se obtin cel mult <tex>2*M</tex> muchii de asteptare.
 
In continuare, se utilizeaza un algoritm de drum de cost minim ("Dijkstra":problema/dijkstra sau "Bellman-Ford":problema/bellmanford) de la nodul de plecare <tex>(1, 0)</tex> la toate celelalte noduri pentru a putea afla costul minim de a ajunge la un anumit aeroport la un anumit moment de timp.
 
Acum pentru fiecare query de forma <tex>(A, T)</tex> (aeroport, timp) se afiseaza minimul dintre distantele pana la toate nodurile <tex>(A, t)</tex>, unde <tex>t <= T</tex> sau <tex>-1</tex> daca nu exista astfel de noduri sau nu pot fi atinse. Pentru asta exista mai multe variante, de exemplu cu sortarea query-urilor si rezolvarea lor offline sau aplicand cautare binara.

h1(#Minlcm). 'C. Minlcm':problema/Minlcm

h1(#Subpermutari). 'H. Subpermutari':problema/Subpermutari

?

Consideram toate cele N² subsecventele are permutarii noastre. Observam faptul ca daca pentru o secventa [a,b] determinam cea mai lunga subpermutare care este atat prefix, cat si sufix a secventei noastre, putem foarte usor marca sufixul ca fiind o secventa care a mai aparut deja si crestem frecventa prefixului.
Pentru a determina cea mai lunga subpermutare care este atat prefix, cat si sufix, vom aplica un algoritm foarte asemanator KMP-ului:
Fixam pozitia de start a subsecventei noastre si pornim algoritmul de KMP de acolo.
Presupunem ca avem calculat pentru o subsecventa [a,b] acest cel mai bun prefix-sufix (il notam identic ca la KMP cu pi[b]). Cand vrem sa trecem la urmatorul element, b + 1, avem aceleasi 2 cazuri de luat in considerare ca si la KMP:
 
Cazul in care elementul inserat b + 1 are aceelasi indice in subpermutarea sufixului ca si urmatorul element in subpermutarea prefixul: pur si simplu pi-ul creste cu 1
Daca indicele difera, micsoram pi-ul (mergem in pi[pi[b]]) si repetam procedeul pana avem o potrivire
 
Pentru a determina al catelea element se afla o valoare intr-o secventa putem usor precalcula cu un simplu aib.
Complexitate: O(N² log N)

h1(#NucleulValoros2). 'I. NucleulValoros2':problema/NucleulValoros2

?

Se consideră: <tex> {\ S[i][j] = V[i] + V[i + 1] + ... + V[j] </tex>
 
<tex> D[i][j] = min(D[i][k] + D[k + 1][j] {\ | {\ i \leq k<j) + S[i][j] </tex>
 
Această recurenţă se poate calcula în <tex>O(N^3)</tex>, dar nu este de ajuns pentru această problemă. Se observă că <tex> S[i][j] </tex> are următoarele proprietăţi:
 
<tex> 1. {\ S[a][c] + S[b][d] \leq S[a][d] + S[b][c] {\ | {\ (a \leq b \leq c \leq d) </tex>
<tex> 2. {\ S[b][c] \leq S[a][d] {\ | {\ (a \leq b \leq c \leq d) </tex>
 
Aceste proprietăţi sunt necesare, dar şi suficiente pentru a aplica optimizarea "Knuth-Yao":http://codeforces.com/blog/entry/8219, care reduce complexitatea la <tex>O(N^2)</tex>