Pentru a calcula {$A[k, i, j]$} ne vom uita fie in {$A[k-1]$} daca {$S1[i] = S2[j] = S3[k]$}, fie in {$A[k]$} ({$S1[i] = S2[j]$}, {$S1[i] != S3[k]$}). Se vor aduna valorile {$A[k (sau k-1), p, q]$} cu {$p<i$}, {$q<j$} si {$S1[p] &le; S1[i]$}.

h3. Solutia O(N*M^2^*P) - 50 puncte

h3. Solutia O(N*M^2*P) - 50 puncte

Se porneste de la solutia anterioara si se observa faptul ca pentru fiecare $q$ care se considera se poate preprocesa suma {$A[k (sau k-1), p, q]$} pentru $p < i$ intr-un tablou {$S$}. Dupa ce se calculeaza {$A[k, i, j]$} considerand doar acele $q$ pentru care {$S2[q] &le; S2[j]$}, se actualizeza {$S[k, j]$}.