Изменения

Модифицируем предыдущее решение, добавив небольшую "хитрость". Теперь <tex> d[i][j] </tex> - это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, причем элемент <tex> b[j] </tex> - последний представитель НОВП, а <tex> a[i] </tex> может не быть таковым. Вычислять <tex> d </tex> будем всё так же: по увеличению <tex> i </tex>, а при равенстве - по увеличению <tex> j </tex>. Тогда для очередного значения <tex> d[i][j] </tex> существу есть два варианта:

*<tex> a[i] </tex> входит в НОВП. Тогда в префиксе Это значит, что <tex> a[i] = b[1..j] > </tex> нужно найти элемент , то есть для подсчёта <tex> bd[ki] = a[ij] </tex>нужно пробегать циклом по <tex> b </tex> в поисках элемента, для которого меньшего <tex> b[j] </tex> с наибольшей <tex> d[i-1][k] \rightarrow max </tex>. А раз Но мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex>, будем считать <tex> a[i] </tex> ''фиксированным''. Чтобы не запускать цикл при каждом равенстве <tex> a[i] </tex> элементу <tex> b[k] </tex>, в дополнительной переменной <tex> best </tex> будем хранить "лучший" элемент (и его индекс <tex> best </tex>_<tex>ind </tex> в массиве <tex> b </tex>) такой, что этот элемент строго меньше <tex> a[i] </tex> (а также меньше <tex> b[i] </tex>) и значение динамики для него максимально.Из этих двух вариантов выберем лучший.