Secv2m
O prima solutie de complexitate O(N3) ar fi alegerea tuturor secventelor de lungime L din cele doua siruri, adunarea lor, alegerea maximului din fiecare set, solutia fiind minimul acestor maxime. Insa, aceasta solutie se poate imbunatati. Astfel, vor suprapune cele doua siruri pentru fiecare pozitie astfel incat sa se obtina toate posibilitatile, si consideram sirul S care va contine A[i] + B[i]. Pentru exemplu, primele suprapuneri arata astfel:
A : 4 3 4 2 2 - - -
B : - - 3 1 3 2 5 3 2
S : - - 7 3 5 - - - -
A : 4 3 4 2 2 - - -
B : - 3 1 3 2 5 3 2
S : - 6 5 5 4 - - -
A : 4 3 4 2 2 - -
B : 3 1 3 2 5 3 2
S : 7 4 7 4 7 - -
A : - 4 3 4 2 2 -
B : 3 1 3 2 5 3 2
S : - 5 6 6 7 5 -
Solutia se obtine folosind structura de date numita Deque, folosindu-se metoda aplicata la problema Secventa.
Se observa ca exista N + M pozitii in care se pot 'aseza' cele doua siruri, iar solutia se obtine in timp liniar, asadar complexitatea finala este O(N2).
