Я нашел код для 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 — последовательность. Я не думаю, что следующий код будет работать, если нам не придется находить «строго» увеличивающиеся последовательности. Можем ли мы изменить код, чтобы найти растущие последовательности, в которых разрешено равенство.
РЕДАКТИРОВАТЬ: алгоритм работает только тогда, когда входные данные различны.
Есть несколько решений для 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.
Я надеюсь, что вы можете сделать шаг индукции самостоятельно 🙂
Код является решением 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;
}
Доказательство относительно простое: рассмотрим множество 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
был исчерпан.
Постановка задачи:
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