Я храню индексы концов и индекс предыдущего для КАЖДОГО элемента A[N]. Память O(N)
> Общее - тоже O(nlogn), вот только память n^2
Такого не может быть, если Вы в каждую ячейку этой памяти хоть раз обращаетесь, то и время O( n^2)
Конкретно, копирование подпоследовательности - это O(N)
Храним только последний элемент от всех префиксов одной подпоследовательности {6},{6,5}...{6,5,4,3} - тут храним только 3 (его индекс) и индекс предыдущего в подпоследовательности (4), индекс предыдущего храним для каждого из A[I] в массиве P[I]
x < хвост L - добав (L,x), L остается, потом к нему может добавится другой y>x
а даже по-Вашему - поменявшийся элемент придется переставить со сдвигом прочих - это O(N) на одно добавление, N^2 на весь алгоритм
Я же писал 2 раза: каждый элемент добавляется только в ОДНУ подпоследователность, следовательно индекс предыдущего ему элемента определен однозначно, его запоминаем в отдельном массиве P[N], впоследствии, зная последний элемент - выписываете его, переходите к предыдущему по индексу итд, пока не выпишите всю подпослед с конца
Непонимаю, как это у вас массив temp вроде упорядочен по последним элементам (раз бинарный поиском проходите) - и как в него тогда добавляете, без потери упорядочеености - нужна вставка за O(N)
Если в списке есть {6,5,4,3,2,1}, то есть и {6,5,4,3,2}, {6,5,4,3}, {6,5,4}, {6,5}, {6}
Так?
Чтобы не хранить все префиксы, храним для каждого элемента ссылку на предудыщий (если он не начальный) - предудыщий однозначно определен, т.к. элемент добавляется ровно в ОДНУ подпоследовательность.
Тогда подпоследовательность однозначно определяется ее последним элементом и легко из него восстанавливается + храните длину для быстрого сравнения
Массивы S[N] - длина подпоследовательности, начинающейся с A[I] и P[N] - индекс элемента подпоследовательности, предшествующего A[I] (он ровно 1) или -1. Подпоследовательность задается индексом I ее последнего элемента, теперь память O(N). Подпоследовательности хранить в MAP - структура с упорядочением, умеющая поиск и добавление за log(N), сортировка по посленему элементу
Все, понял! Если новый элемент X=хвосту какой либо подпоследовательности L, то L заменяем на (L,X), если X < хвоста L, то для такого L с max длиной добавляем подпоследовательность (L,X). Получается для любой подпоследовательности L в списке также присутствуют и все ее префиксы (некоторое кол-во первых элементов, включая только одну голову). Если же X > всех хвостов (т.е. и голов), то добавляем подпоследовательность X из одного эл-та. Действительно, подпоследовательностей L всегда I на I-той итерации, насчет длины - ошибка. Для поиска и вставки за log(N) нужен MAP с сортировкой по хвосту. Однако память используется прожорливо, для хранения всех префиксов L, помоему к стремится O(N^2)
Новый элемент можно присоединить к хвосту ЛЮБОЙ подпоследовательности, если он меньше, а можно и не присоединять
Быстрый рост числа вариантов
Может я по прежнему не понимаю Ваш алгоритм
Python-овское добавление в список (массив) не O(1) - не в этом ли причина просадки?
Непонимаю Вас, A[0] может быть началом резельтирующей подпоследовательности, A[I]>A[0], I>0 также может и A[I2]>A[I], I2>I итд - возрастающая подпоследовательность - все кандидаты в начальные элементы
Написано
Войдите на сайт
Чтобы задать вопрос и получить на него квалифицированный ответ.
Я пока расчитываю на сжатие