Изменения

Построим следующую динамику: <tex> d[i][j] </tex> - это длина наибольшей возрастающей подпоследовательности массивов <tex> a </tex> и <tex> b </tex>, последний элемент которой <tex> a[i] </tex> и <tex> b[j] (a[i] = b[j]) </tex>. Будем заполнять <tex> d[i][j] </tex> сначала по увеличению <tex> i </tex>, а при равенстве по увеличению <tex> j </tex>. Ответом на задачу будет максимум из всех элементов <tex> d[i][j] </tex>, (где <tex> i = 1...n </tex>, <tex> j = 1...m. </tex>)

Если <tex> a[i] = b[j] </tex>, то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах <tex> a </tex> и <tex> b </tex>. Заметим, что предыдущие значения <tex> d </tex> уже известны, тогда очередное значение <tex> d[i][j] = max(d[k][l] + 1, </tex> для всех <tex> k = 1..i-1 </tex> и <tex> l = 1..j-1), </tex> при условии, что <tex> a[k] = b[l] </tex>

vector<int> LCIS(vector<int> a[n], vector<int> b[m] ) d= int[n][m] //динамика prev= int[n] //массив предков inputData(a, n) inputData(b, m)

d[i][j] := 1 //НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]

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

b_i := i b_j := j print(d[b_i][b_j]) //размер НОВПvector<int> answer pos := b_i //проходим по массиву a, выписывая элементы НОВП

printanswer.push(a[pos]) pos := prev[pos] '''return''' answer