алгоритм — самая длинная включающая подпоследовательность, использующая std :: set в переполнении стека

Я нашел код для LIS в книге, я не совсем в состоянии выработать доказательство правильности. Может ли кто-нибудь помочь мне с этим. Все, что делает код, — это удаляет элемент рядом с новым вставленным элементом в наборе, если новый элемент не является максимальным, иначе просто вставляет новый элемент.

    set<int> s;
set<int>::iterator it;
for(int i=0;i<n;i++)
{
s.insert(arr[i]);
it=s.find(arr[i]);
it++;
if(it!=s.end())
s.erase(it);
}
cout<<s.size()<<endl;

n — размер последовательности, а arr — последовательность. Я не думаю, что следующий код будет работать, если нам не придется находить «строго» увеличивающиеся последовательности. Можем ли мы изменить код, чтобы найти растущие последовательности, в которых разрешено равенство.

РЕДАКТИРОВАТЬ: алгоритм работает только тогда, когда входные данные различны.

2

Решение

Есть несколько решений для LIS.
Наиболее типичным является алгоритм O (N ^ 2), использующий динамическое программирование, где для каждого индекса i вычисляется «самая длинная возрастающая последовательность, заканчивающаяся индексом i».
Вы можете ускорить это до O (N log N), используя умные структуры данных или двоичный поиск.

Ваш код обходит это и рассчитывает только длину LIS.
Рассмотрим ввод «1 3 4 5 6 7 2», содержимое набора в конце будет «1 2 4 5 6 7», что не является LIS, но длина верна.
Доказательство должно идти с использованием индукции следующим образом:

После i-й итерации j-й наименьший элемент является наименьшим возможным концом увеличивающейся последовательности длины j в первых i-х элементах массива.

Рассмотрим ввод «1 3 2». После второй итерации мы установили «1 3», поэтому 1 — это наименьший возможный конец увеличивающейся последовательности длины 1, а 3 — наименьший возможный конец увеличивающейся последовательности длины 2.
После третьей итерации мы установили «1 2», где теперь 2 — это наименьший возможный конец возрастающей последовательности длины 2.

Я надеюсь, что вы можете сделать шаг индукции самостоятельно 🙂

3

Другие решения

Код является решением O (nlogn) для LIS, но вы хотите найти не строго возрастающую последовательность, у реализации есть проблема, потому что std :: set не допускает дублирования элемента. Вот код, который работает.

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int main()
{
int arr[] = {4, 4, 5, 7, 6};
int n = 5;
multiset<int> s;
multiset<int>::iterator it;
for(int i=0;i<n;i++)
{
s.insert(arr[i]);
it = upper_bound(s.begin(), s.end(), arr[i]);
if(it!=s.end())
s.erase(it);
}
cout<<s.size()<<endl;
return 0;
}
2

Доказательство относительно простое: рассмотрим множество s как отсортированный список. Мы можем доказать это с инвариант цикла. После каждой итерации алгоритма s[k] содержит наименьший элемент arr заканчивающийся восходящей подпоследовательностью длины k в подмассиве от нуля до последнего элемента arr что мы рассмотрели до сих пор. Мы можем доказать это по индукции:

  • После первой итерации это утверждение верно, потому что s будет содержать ровно один элемент, который является тривиальной восходящей последовательностью одного элемента.
  • Каждая итерация может изменить набор одним из двух способов: она может расширить его на единицу в случаях, когда arr[i] самый большой найденный элемент, или замените существующий элемент на arr[i], который меньше, чем элемент, который был там раньше.

Когда происходит расширение набора, это происходит потому, что текущий элемент arr[i] может быть добавлен к текущей LIS. Когда замена происходит в положении k, индекс arr[i]это происходит потому, что arr[i] заканчивается восходящая подпоследовательность длины kи меньше или равно старому s[i] что раньше заканчивалось предыдущей «лучшей» восходящей подпоследовательностью длины k,

С этим инвариантом в руке легко увидеть, что s содержит столько элементов, сколько самой длинной восходящей подпоследовательности arr после всего arr был исчерпан.

1

Постановка задачи:

  For A(n) :a0, a1,….an-1 we need to find LIS

Find all elements in A(n) such that, ai<aj and i<j.
For example: 10, 11, 12, 9, 8, 7, 5, 6
LIS will be 10,11,12

Это решение O (N ^ 2), основанное на DP.

1 Finding SubProblems
Consider D(i): LIS of (a0 to ai) that includes ai as a part of LIS.
2 Recurrence Relation
D(i) = 1 + max(D(j) for all j<i) if ai > aj
3 Base Case
D(0) = 1;

Проверьте ссылку на код:
http://wp.me/p3bJAF-W

-1
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector