Изменения

d = int[n][m] // динамика prev = int[n] // массив предков '''for''' i = 1...n '''for''' j = 1...m '''if''' a[i] == b[j] d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j] '''for''' k = 1...i-1 '''for''' l = 1...j-1 '''if''' a[k] == b[l] '''and''' a[k] < a[i] '''and''' d[i][j] < d[k][l] + 1 d[i][j] = d[k][l] + 1 prev[i] = k // восстановление b_i = 1 // ищем лучшую пару (b_i, b_j) b_j = 1 // d[b_i][b_j] <tex> \rightarrow </tex> max '''for''' i = 1...n '''for''' j = 1...m '''if''' d[b_i][b_j] < d[i][j] b_i = i b_j = j vector<int> answer pos = b_i // проходим по массиву a, выписывая элементы НОВП '''while''' pos != 0 answer.push(a[pos]) pos = prev[pos] '''return''' answer