Изменения
→Решение за время O(N2)
Пусть теперь <tex> d[i][j] </tex> - это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex> (элементы <tex> a[i] </tex> и <tex> b[j] </tex> могут не входить в НОВП). Вычислять <tex> d </tex> будем по увеличению <tex> i </tex>, а при равенстве - по увеличению <tex> j </tex>. Заметим, что в предыдущем решении при каждом равенстве элементов <tex> a[i] </tex> и <tex> b[j] </tex> приходилось пробегать дополнительным циклом по массиву <tex> a </tex> в поисках элемента, меньшего <tex> a[i] </tex>, для которого <tex> d[k][j] </tex> на префиксе <tex> a[1..k] </tex> и <tex> b[1..j] </tex> была наилучшей. А раз мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex> , то <tex> a[i] </tex> можно считать фиксированным, а <tex> b[j] </tex> - переменным. Тогда давайте в дополнительной переменной хранить лучший элемент и его индекс в массиве <tex> b </tex>, такой, что этот элемент строго меньше <tex> a[i] </tex> и значение динамики для него максимально. Фактически, это решение отличается от предыдущих только более "хитрой" реализацией.
vector<int> '''LCIS'''(vector<int> a, vector<int> b) d= int[n][m]// динамика prev= int[mn]// массив предков '''for''' i = 1...n best_ind := 0 //позиция "лучшего" элемента в массиве b best := 0 //значение динамики для "лучшего" элемента '''for''' j = 1...m d[i][j] := d[i-1][j] //НОВП на префиксе a[1..i-1] и b[1..j], то есть без элемента a[i] '''if''' a[i] == b[j] '''and''' d[i-1][j] < best + 1 //можем использовать a[i]-тый элемент для увеличения НОВП d[i][j] := best + 1 p[j] := best_ind '''if''' a[i] > b[j] '''and''' d[i-1][j] > best //в момент следующего равенства a[i] = b[j'] нам не придётся бежать циклом в поисках элемента k: best := d[i-1][j] //b[k] < b[j'] = a[i]. Мы считаем элемент a[i] фиксированным и сравниваем кандидатов с ним best_ind := j //восстановление (по массиву b) b_j := 1 //ищем лучший элемент d[n][b_j]<tex> \rightarrow </tex> max '''for''' k = 1...m '''if''' d[n][b_j] < d[n][j] b_j := j print(d[n][b_j]) //размер НОВП vector<int> answer pos := b_j //проходим по массиву b, выписывая элементы НОВП '''while''' pos != 0 print answer.push(b[pos]) pos := prev[pos] '''return''' answer
== См. также ==
