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

Question

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

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). Если я попытаюсь работать с несколькими тестовыми случаями, похоже, это сработает. Но я все еще не мог понять его логику правильности. Кроме того, это не выглядит так интуитивно для меня.

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

Answer 1

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

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

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

Answer 2

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

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

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

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

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

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

2. A[i] A[i]). Что является правдой. Отсюда доказано.

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