Cel mai lung subșir comun

Cerință:

Fie v un vector cu N elemente. Se numeste subșir de lungime K al vectorului v un nou vector v' = (vi1, vi2, ... viK), cu i1 < i2 < ... < iK. De exemplu, vectorul v = (5 7 8 9 1 6) contine ca subșir șirurile (5 8 6) sau (7 8 1), dar nu contine sușirul (1 5). Se dau doi vectori A si B cu elemente numere naturale nenule. Să se determine subșirul de lungime maximă care apare atât in A cât și în B.

Rezolvare:

Soluția optimă se bazează pe metoda programării dinamice. Construim o  matrice DP cu semnificația DPi, j = lungimea maxima a unui subșir comun care există în A până pe poziția I și în B până pe poziția j. Initial, matricea este nulă. Complexitate: O(N * M) timp și O(N * M) memorie.

​

#include <iostream>

using namespace std;

const int maxn = 1030;

int A[maxn], B[maxn], Ans[maxn], Dp[maxn][maxn], lg;

int main() {

    int n, m, i, j;

    cin >> n >> m;

    for (i = 1; i <= n; i++) {

        cin >> A[i];

    }

    for (i = 1; i <= m; i++) {

        cin >> B[i];

    }

    for (i = 1; i <= n; i++) {

        for (j = 1; j <= m; j++) {

            if (A[i] == B[j]) {

                Dp[i][j] = Dp[i - 1][j - 1] + 1;

            } else {

                Dp[i][j] = max(Dp[i - 1][j], Dp[i][j - 1]);

            }

        }

    }

    i = n, j = m;

    while (i && j) {

        if (A[i] == B[j]) {

            Ans[++lg] = A[i];

            i--;

            j--;

        } else if (Dp[i - 1][j] > Dp[i][j - 1]) {

            i--;

        } else {

            j--;

        }

    }

    cout << lg << "\n";

    for (i = lg; i; i--) {

        cout << Ans[i] << " ";

    }

    return 0;

}