Задача о наибольшей общей возрастающей последовательности
Построим следующую динамику: [math] d[i][j] [/math] — это длина наибольшей возрастающей подпоследовательности массивов [math] a [/math] и [math] b [/math] , последний элемент которой [math] a[i] [/math] и [math] b[j] (a[i] = b[j]) [/math] . Будем заполнять [math] d[i][j] [/math] сначала по увеличению [math] i [/math] , а при равенстве по увеличению [math] j [/math] . Ответом на задачу будет максимум из всех элементов [math] d[i][j] [/math] (где [math] i = 1. n [/math] , [math] j = 1. m. [/math] )
Заполнять [math] d [/math] будем следующим образом: на очередном шаге сравниваем элементы [math] a[i] [/math] и [math] b[j] [/math] :
- Если [math] a[i] \neq b[j] [/math] , то [math] d[i][j] = 0 [/math] (так как нет НОВП, оканчивающейся в разных элементах).
- Если [math] a[i] = b[j] [/math] , то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах [math] a [/math] и [math] b [/math] . Заметим, что предыдущие значения [math] d [/math] уже известны, тогда очередное значение [math] d[i][j] = \max\limits_ d[k][l] + 1 [/math] при условии, что [math] a[k] = b[l]. [/math]
Длина НОВП будет в элементе с максимальным значением [math] d[i][j] [/math] . Для восстановления подпоследовательности можно хранить массив предков [math] prev[1..n] [/math] массива [math] a: prev[i] [/math] — индекс предыдущего элемента НОВП, которая оканчивается в [math] a[i] [/math] .
vector LCIS(a: int[n], b: int[m]) for i = 1 to n for j = 1 to m if a[i] == b[j] d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] b[j] for k = 1 to i - 1 for l = 1 to 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_j = 1 for i = 1 to n for j = 1 to m if d[b_i][b_j] < d[i][j] b_i = i b_j = j pos = b_i // проходим по массиву a, выписывая элементы НОВП answer: vector while pos 0 answer.pushBack(a[pos]) pos = prev[pos] return answer Решение за время O(n 2 × m)
Улучшим предыдущее решение. Пусть теперь [math] d[i][j] [/math] — динамика, в которой элемент [math] a[i] [/math] по-прежнему последний представитель НОВП массива [math] a [/math] , а [math] b[j] [/math] может не быть быть последним представителем массива [math] b [/math] :
- Если [math] a[i] \neq b[j] [/math] , будем «протаскивать» последнее удачное сравнение в динамике: [math] d[i][j] = d[i][j-1] [/math] (понять это можно так: [math] a[i] \neq b[j] [/math] , поэтому [math] b[j] [/math] не последний представитель НОВП из массива [math] b [/math] , а значит предыдущий элемент НОВП находится в префиксе [math] b[1..j-1] [/math] , но [math] d[i][j-1] [/math] уже посчитан).
- Если [math] a[i] = b[j] [/math] , то одним дополнительным циклом пробежим по [math] a [/math] и найдём предыдущий элемент НОВП, оканчивающейся в [math] a[i] [/math] (он меньше [math] a[i] [/math] ). Из подходящих элементов выберем тот, для которого [math] d[k][j] [/math] — максимальна.
[math] d[i][j] = \max\limits_ d[k][j] + 1 [/math] при условии, что [math] a[k] \lt a[i].[/math]
Длина НОВП будет в элементе с максимальным значением [math] d[i][m] [/math] . Для восстановления ответа будем хранить массив предков по массиву [math] a [/math] , как и в предыдущем решении.
vector LCIS(a: int[n], b: int[m]) for i = 1 to n for j = 1 to m if a[i] == b[j] d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] b[j] for k = 1 to i - 1 if a[k] < a[i] and d[i][j] < d[k][j] + 1 d[i][j] = d[k][j] + 1 prev[i] = k else d[i][j] = d[i][j - 1] // восстановление pos = 1 // ищем элемент c максимальным d[pos][m] for i = 1 to n if d[pos][m] < d[i][m] pos = i // проходим по массиву a, выписывая элементы НОВП answer: vector while pos 0 answer.pushBack(a[pos]) pos = prev[pos] return answer Решение за время O(n × m)
Модифицируем предыдущее решение, добавив небольшую хитрость. Теперь [math] d[i][j] [/math] — это длина наибольшей общей возрастающей подпоследовательности префиксов [math] a[1..i] [/math] и [math] b[1..j] [/math] , причем элемент [math] b[j] [/math] — последний представитель НОВП массива [math] b [/math] , а [math] a[i] [/math] может не быть последним в массиве [math] a [/math] . Вычислять [math] d [/math] будем всё так же: сначала по увеличению [math] i [/math] , а при равенстве — по увеличению [math] j [/math] . Тогда для очередного значения [math] d[i][j] [/math] есть два варианта:
- [math] a[i] [/math] не входит в НОВП. Тогда [math] d[i][j] = d[i-1][j] [/math] : значение динамики уже посчитано на префиксе [math] a[1..i-1] [/math] .
- [math] a[i] [/math] входит в НОВП. Это значит, что [math] a[i] = b[j] [/math] , то есть для подсчёта [math] d[i][j] [/math] нужно пробегать циклом по [math] b [/math] в поисках элемента [math] b[k] \lt b[j] [/math] с наибольшим значением [math] d[i-1][k] [/math] . Но мы считаем [math] d [/math] сначала по увеличению [math] i [/math] , поэтому будем считать [math] a[i] [/math] фиксированным. Чтобы не запускать цикл при каждом равенстве [math] a[i] [/math] элементу [math] b[k] [/math] , в дополнительной переменной [math] best [/math] будем хранить «лучший» элемент (и его индекс [math] ind [/math] в массиве [math] b [/math] ) такой, что этот элемент строго меньше [math] a[i] [/math] (а также меньше [math] b[k] [/math] ) и значение динамики для него максимально: [math] b[ind] \lt a[i] = b[j] [/math] и [math] best = d[i-1][ind] \rightarrow max. [/math]
vector LCIS(a: int[n], b: int[m]) for i = 1 to n ind = 0 // позиция "лучшего" элемента в массиве b best = 0 // значение динамики для "лучшего" элемента for j = 1 to 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 prev[j] = ind if a[i] > b[j] and d[i - 1][j] > best // при следующем равенстве a[i] == b[j'] best = d[i - 1][j] // в best будет храниться "лучший" элемент ind = j // b[ind] < b[j'] и d[i-1][ind] max // восстановление (по массиву b) pos = 1 // ищем лучший элемент d[n][pos] max for j = 1 to m if d[n][pos] < d[n][j] pos = j // проходим по массиву b, выписывая элементы НОВП answer: vector while pos 0 answer.pushBack(b[pos]) pos = prev[pos] return answer
Доказательство оптимальности
В данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев [math] a[i] = b[j] [/math] не влияет на корректность алгоритма — это всего лишь уловки реализации. Поэтому покажем, что для вычисления очередного значения [math] d[i][j] [/math] мы используем оптимальность на подзадачах и обращаемся к уже посчитанным значениям. Напомним, как обозначается динамика: [math] d[i][j] [/math] — это НОВП на префиксах [math] a[1..i] [/math] и [math] b[1..j] [/math] , где последним элементом НОВП является элемент [math] b[j] [/math] , а [math] a[i] [/math] может не быть равен [math] b[j] [/math] (то есть элемент [math] a[i’] = b[j] [/math] лежит где-то в префиксе [math] a[1..i] [/math] ). Итак, для [math] d[i][j] [/math] есть два варианта:
- [math] a[i] \neq b[j] [/math] , тогда [math] a[i] [/math] не влияет на результат, и последний элемент НОВП [math] a[i’] = b[j] [/math] лежит в [math] a[1..i-1] [/math] .
- [math] a[i] = b[j] [/math] , тогда [math] a[i] [/math] и [math] b[j] [/math] — последние элементы НОВП префиксов [math] a[1..i] [/math] и [math] b[1..j] [/math] : [math] b[j] [/math] — по определению динамики, а [math] a[i] [/math] как элемент, который может стать последним, не ухудшая результат. Действительно, последовательность строго возрастает, поэтому если в префиксе [math] a[1..i-1] [/math] есть элемент [math] a[k] = b[j] [/math] , то его можно заменить на элемент [math] a[i] [/math] без уменьшения длины НОВП. Если же в [math] a[1..i-1] [/math] такого элемента нет, то [math] a[i] [/math] — единственный из возможных вариантов. Итак, [math] a[i] [/math] и [math] b[j] [/math] — последние элементы НОВП. Значит, начало НОВП ( [math] d[i][j] [/math] ) лежит в префиксах [math] a[1..i-1] [/math] и [math] b[1..j-1] [/math] (значения для которых уже посчитаны). Мы ищем элемент [math] b[k] \lt b[j] [/math] с лучшей динамикой [math] d[i-1][k] [/math] , что удовлетворяет условию возрастания последовательности и автоматически гарантирует, что конец такой НОВП лежит в префиксе [math] a[1..i-1] [/math] .
См. также
Источники информации
Источник
Наибольшая возрастающая последовательность на отрезке
В общем нужно реализовать структуру для поиска наибольшей возрастающей подпоследовательности на отрезке. Количество чисел в массиве около 200 тысяч. Поисков нвп нужно выполнить тоже около 200 тысяч раз.
Поглядываю на дерево отрезков, но как не пытаюсь, никак не получается реализовать вообще.
Наибольшая возрастающая подпоследовательность
Дна последовательность, нужно найти её наибольшую возрастающую подпоследовательность. Входные.
Наибольшая возрастающая подпоследовательность за O(NlogN)
Здравствуйте! Вот тут написал код НВП за О(NlogN).Но на тестирующей системе он выдает на тесты.
Наибольшая возрастающая подпоследовательность (LIS)
Доброго времени суток! Я не сильно разбираюсь в шарпе(совсем) и при выполнении одного задания.
Сообщение от ThePonyCoder 
Сообщение от ThePonyCoder
В общем нужно реализовать структуру для поиска наибольшей возрастающей подпоследовательности на отрезке. Количество чисел в массиве около 200 тысяч. Поисков нвп нужно выполнить тоже около 200 тысяч раз.
Пример:
Есть массив
Задаём границы отрезков.
L1 = 1. R1 = 3
Макс НВП здесь будет
L2 = 5. R2 = 7
НВП
L3 = 4. R2 = 7
НВП
Сообщение от Shamil1
Возрастающая последовательность
Задание: Написать программу, которая проверяет, представляют ли элементы введенного с клавиатуры.
Возрастающая последовательность
Дано n вещественных чисел, определите, образует ли она длину возрастающей последовательности
возрастающая последовательность
необходимо удалить из заданного массива 4 элемента так, чтобы оставшиеся образовали возрастающую.
Возрастающая последовательность
Ребят, помогите написать скрипт, нужно определить, образуют ли набранные в командной строке числа.
Источник