Занятие 5. Справочник

static long[][] lcs;
static pair[][] prev;
static int n;
static int m;

static void findLCS(long[] a, long[] b)
{
    for (int i = 0; i < n; i++) lcs[i][0] = 0;
    for (int i = 0; i < m; i++) lcs[0][i] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) {
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
                prev[i][j] = new pair(i - 1, j - 1);
            } else {
                if (lcs[i - 1][j] >= lcs[i][j - 1]) {
                    lcs[i][j] = lcs[i - 1][j];
                    prev[i][j] = new pair(i - 1, j);
                } else {
                    lcs[i][j] = lcs[i][j - 1];
                    prev[i][j] = new pair(i, j - 1);
                }
            }
        }
    }
}

class pair 
{
    public pair(long a, long b) 
    {
        firstp = a;
        secpair = b;
    }
    long firstp;
    long secpair;
}

static void findBackWay(long[] a) throws IOException {
    ArrayDeque queue = new ArrayDeque();
    pair curr = new pair(n, m);
    while (curr.firstp != 0 && curr.secpair != 0) {
        pair sec = prev[((int) curr.firstp)][((int) curr.secpair)];
            if (sec.firstp == curr.firstp - 1 && sec.secpair == curr.secpair - 1)
            queue.add(a[((int) curr.firstp - 1)]);
        curr = sec;
    }
    while (!queue.isEmpty()) out.print(queue.pollLast()+ " ");
}