Revizia anterioară Revizia următoare
Secv2m
Se 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).