Как работает алгоритм самой длинной возрастающей подпоследовательности [O(nlogn)]?

Я нашел алгоритм, упомянутый в Автостопом по соревнованиям по программированию (примечание: эта реализация предполагает наличие в списке нет дубликатов):

set<int> st;
set<int>::iterator it;
st.clear();

for(i=0; i<n; i++) {

  st.insert(array[i]); it=st.find(array[i]);

  it++; if(it!=st.end()) st.erase(it);
}

cout<<st.size()<<endl;

Это алгоритм поиска самой длинной возрастающей подпоследовательности за O(NlogN). Если я попытаюсь работать с несколькими тестовыми примерами, это, кажется, сработает. Но я все еще не мог понять логику его правильности. Кроме того, мне это не кажется таким уж интуитивным.

Может ли кто-нибудь помочь мне понять, почему этот алгоритм работает правильно?


algorithm lis proof-of-correctness correctness
person aamir    schedule 14.12.2013    source источник
comment
Подсказка: прочитайте о Dynamic programming, memoization, а также об этом ocw.mit.edu/courses/electrical-engineering-and-computer-science/   -  person noMAD    schedule 15.12.2013
comment
Насколько я знаю, решение для динамического программирования - O (n * n).   -  person aamir    schedule 15.12.2013
comment
@AamirKhan Динамическое программирование - это общий метод решения проблем, его применение может привести к решениям с очень разной временной сложностью в зависимости от проблемы и того, как вы ее применили. Например, динамическое программирование Фибоначчи — это линейное время.   -  person    schedule 15.12.2013
comment
В этом прелесть этого алгоритма. Это даст вам правильную длину LIS, но элементы в наборе не обязательно должны быть теми, которые составляют ее! В этом случае алгоритм вернет 5 в качестве ответа, хотя набор будет иметь элементы {1,2,4,7,9}   -  person aamir    schedule 15.12.2013
comment
Длина наибольшей цепи равна размеру наименьшего покрытия антицепями (терема Дилуорта). Вы можете показать, что для этого частичного множества жадное нахождение антицепного покрытия дает оптимальное решение.   -  person tmyklebu    schedule 15.12.2013

Ответы (2)


arrow_upward
2
arrow_downward

Как определить самую длинную возрастающую подпоследовательность, используя динамическое программирование?

Сначала прочтите мое объяснение там. Если это все еще не ясно, прочитайте следующее:

Алгоритм сохраняет наименьшее возможное конечное число для LIS каждой длины. Сохраняя наименьшие числа, вы можете максимально расширить LIS. Я знаю, что это не доказательство, но, возможно, это будет интуитивно понятно для вас.

person Petar Minchev    schedule 14.12.2013

arrow_upward
4
arrow_downward

Утверждение: для каждого i длина текущего набора равна длине наибольшей возрастающей подпоследовательности.

Доказательство: воспользуемся методом индукции:

Базовый случай: тривиально верно.

Гипотеза индукции: Предположим, мы обработали i-1 элементов, и длина набора равна LIS[i-1], т.е. возможная длина LIS с первыми i-1 элементами.

Шаг индукции: вставка элемента array[i] в ​​набор приведет к двум случаям.

  1. A[i] >= set.last() : в этом случае A[i] будет последним элементом в наборе и, следовательно, LIS[i] = LIS[i-1]+1.

  2. A[i] ‹ set.last() : в этом случае мы вставляем A[i] в ​​набор и удаляем элемент чуть больше A[i] в ​​порядке сортировки. LIS[i] = LIS[i-1] + 1 (добавление A[i]) - 1 (удаление одного элемента > A[i]). Что является правдой. Значит доказано.

Чтобы объяснить общую картину. Вставка A[i] в ​​набор либо добавит к LIS[i-1], либо создаст собственную LIS, которая будет элементами от 0-й позиции до позиции i-го элемента.

person tranquil    schedule 02.05.2014