Комментарии 12
С помощью этого алгоритма мы будем искать место для нового элемента в подпоследовательности.
Тут у вас неправильное объяснение. Если мы действительно вставляем новый элемент в середину этого массива, то он уже не будет подпоследовательностью, потому что элементы тут будут идти не по порядку их положения в изначальном массиве.
На самом деле этот отсортированный массив — не подпоследовательность. Тут мы просто храним для каждой длины подпоследовательности минимальный элемент, на котором она может заканчиваться.
Очевидно, что этот массив всегда будет отсортирован возрастанию. Немного подумав можно также понять, что новый элемент может перезаписать ровно одно место в массиве, котрое как раз и можно найти бинарным поиском.
Еще один плюс этого алгоритма: он находит не только длину максимальной возрастающей подпоследовательности, но и саму подпоследовательность.Но ведь полученная «подпоследовательность» (3, 6, 7, 8) не является подпоследовательностью изначальной последовательности (5, 10, 6, 12, 3, 24, 7, 8). Длину мы находим правильно, но в процессе меняем элементы в середине подпоследовательности, и, следовательно, она становится невалидной
Мы знаем размер максимальной подпоследовательности — это 4. Тогда мы берем 8 элемент 8 — у него индекс равен 4 — 1 = 3. Идем в лево по массиву indexes — следующий элемент — 7 (у него indexes = 2), потом нам нужен 6 — у него indexes = 1, следующий 5, у него indexes = 0. Выбираем элементы которые соответствуют убыванию indexes. (получаем 5, 6, 7, 8). Спасибо
Кстати всё это весьма неплохо описано в e-maxx.ru/algo/longest_increasing_subseq_log Я лично за O(n log n) чаще использовал способ с деревом Фенвика.
# тестовые данные:
testdata <- floor(runif(10000, min = 1, max = 10))
# вспомогательный датафрейм:
temp_data <- data.frame(testdata)
temp_data$prev[2:nrow(temp_data)] <- temp_data$testdata[1:nrow(temp_data)-1]
temp_data$diff_prev <- temp_data$testdata - temp_data$prev
temp_data$incr <- ifelse(temp_data$diff_prev > 0 , 1, 0) # показатель возрастания
# преобразование в строку
str <- paste(temp_data$incr, collapse = "")
library(stringr)
str_vector <- str_split(str, "0")[[1]]
# длинa самой большой возрастающей подпоследовательности в массиве:
max(nchar(str_vector )) + 1
# тестовые данные:
testdata < — floor(runif(10000, min = 1, max = 10))
# длинa самой большой возрастающей подпоследовательности в массиве:
max(diff(grep(0, ifelse(diff(testdata)>0,1,0))))
Вы нашли самую большую возрастающую подстроку. А тут решается задача о подпоследовательности. Разница в том, что в подпоследовательности элементы могут идти не подряд, а с пропусками.
Теперь когда задача определена, решать мы ее начинаем с (сюрприз!) вычисления чисел Фибоначчи, ибо вычисление их — это самый простой алгоритм, в котором используется “динамическое программирование”. ДП — термин, который лично у меня никаких правильных ассоциаций не вызывает, я бы назвал этот подход так — “Программирование с сохранением промежуточного результата этой же задачи, но меньшей размерности”.
Очень правильные вводные слова, а то для меня тоже - динамическое программирование - это термин, усложняющий понимание самой сути решения задачи
Решаем задачу нахождения длины наибольшей возрастающей подпоследовательности