Есть одна вещь, которую я не могу понять:
почему X [M [i]] неубывающая последовательность?
Наибольшая возрастающая подпоследовательность (O (nlogn))
Ответ 1
Сначала рассмотрим алгоритм n ^ 2:
dp[0] = 1;
for( int i = 1; i < len; i++ ) {
dp[i] = 1;
for( int j = 0; j < i; j++ ) {
if( array[i] > array[j] ) {
if( dp[i] < dp[j]+1 ) {
dp[i] = dp[j]+1;
}
}
}
}
Теперь улучшение происходит во втором цикле, в основном, вы можете улучшить скорость, используя двоичный поиск. Помимо массива dp [], пусть имеется еще один массив c [], c является довольно особенным, c [i] означает: минимальное значение последнего элемента самой длинной увеличивающейся последовательности, длина которой равна i.
sz = 1;
c[1] = array[0]; /*at this point, the minimum value of the last element of the size 1 increasing sequence must be array[0]*/
dp[0] = 1;
for( int i = 1; i < len; i++ ) {
if( array[i] < c[1] ) {
c[1] = array[i]; /*you have to update the minimum value right now*/
dp[i] = 1;
}
else if( array[i] > c[sz] ) {
c[sz+1] = array[i];
dp[i] = sz+1;
sz++;
}
else {
int k = binary_search( c, sz, array[i] ); /*you want to find k so that c[k-1]<array[i]<c[k]*/
c[k] = array[i];
dp[i] = k;
}
}
Ответ 2
Это решение O (n * lg (n)) из Руководство автостопом по программированию (примечание: эта реализация предполагает нет дубликатов в списке):
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;
Чтобы учесть дубликаты, можно проверить, например, если номер уже установлен. Если это так, проигнорируйте число, в противном случае используйте тот же метод, что и раньше. В качестве альтернативы можно было бы изменить порядок операций: сначала удалите, затем вставьте. В приведенном ниже коде реализовано следующее:
set<int> st;
set<int>::iterator it;
st.clear();
for(int i=0; i<n; i++) {
it = st.lower_bound(a[i]);
if (it != st.end()) st.erase(it);
st.insert(a[i]);
}
cout<<st.size()<<endl;
Второй алгоритм может быть расширен, чтобы найти самую длинную возрастающую подпоследовательность (LIS), поддерживая родительский массив, который содержит положение предыдущего элемента LIS в исходном массиве.
typedef pair<int, int> IndexValue;
struct IndexValueCompare{
inline bool operator() (const IndexValue &one, const IndexValue &another){
return one.second < another.second;
}
};
vector<int> LIS(const vector<int> &sequence){
vector<int> parent(sequence.size());
set<IndexValue, IndexValueCompare> s;
for(int i = 0; i < sequence.size(); ++i){
IndexValue iv(i, sequence[i]);
if(i == 0){
s.insert(iv);
continue;
}
auto index = s.lower_bound(iv);
if(index != s.end()){
if(sequence[i] < sequence[index->first]){
if(index != s.begin()) {
parent[i] = (--index)->first;
index++;
}
s.erase(index);
}
} else{
parent[i] = s.rbegin()->first;
}
s.insert(iv);
}
vector<int> result(s.size());
int index = s.rbegin()->first;
for(auto iter = s.rbegin(); iter != s.rend(); index = parent[index], ++iter){
result[distance(iter, s.rend()) - 1] = sequence[index];
}
return result;
}
Ответ 3
Нам нужно поддерживать списки возрастающих последовательностей.
В общем случае мы имеем множество активных списков различной длины. Мы добавляем в эти списки элемент A [i]. Мы сканируем списки (для конечных элементов) в порядке убывания их длины. Мы проверим конечные элементы всех списков, чтобы найти список, конечный элемент которого меньше A [i] (значение пола).
Наша стратегия определяется следующими условиями:
1. Если A [i] наименьший среди всех конечных кандидатов активных списков, мы запустим новый активный список длины 1.
2. Если A [i] является самым большим среди всех конечных кандидатов активных списков, мы будем клонировать самый большой активный список и расширять его на A [i].
3. Если A [i] находится между ними, мы найдем список с наибольшим конечным элементом, который меньше A [i]. Клонировать и расширить этот список на A [i]. Мы отбросим все остальные списки той же длины, что и в этом измененном списке.
Обратите внимание, что в любом случае при создании активных списков сохраняется следующее условие.
"конечный элемент меньшего списка меньше конечных элементов более крупных списков".
В этом примере будет ясно, возьмем пример из wiki:
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.
A [0] = 0. Случай 1. Нет активных списков, создайте их.
0.
----------------------------------------------- ------------------------------
A [1] = 8. Случай 2. Клонирование и расширение.
0.
0, 8.
----------------------------------------------- ------------------------------
A [2] = 4. Случай 3. Клонировать, расширять и отбрасывать.
0.
0, 4.
0, 8. Отброшено
----------------------------------------------- ------------------------------
A [3] = 12. Случай 2. Клонирование и расширение.
0.
0, 4.
0, 4, 12.
----------------------------------------------- ------------------------------
A [4] = 2. Случай 3. Клонировать, продлить и отменить.
0.
0, 2.
0, 4. Отброшено.
0, 4, 12.
----------------------------------------------- ------------------------------
A [5] = 10. Случай 3. Клонировать, продлить и отменить.
0.
0, 2.
0, 2, 10.
0, 4, 12. Отброшено.
----------------------------------------------- ------------------------------
A [6] = 6. Случай 3. Клонировать, продлить и отменить.
0.
0, 2.
0, 2, 6.
0, 2, 10. Отброшено.
----------------------------------------------- ------------------------------
A [7] = 14. Случай 2. Клонирование и расширение.
0.
0, 2.
0, 2, 6.
0, 2, 6, 14.
----------------------------------------------- ------------------------------
A [8] = 1. Случай 3. Клонировать, продлить и выбросить.
0.
0, 1.
0, 2. Отброшено.
0, 2, 6.
0, 2, 6, 14.
----------------------------------------------- ------------------------------
A [9] = 9. Случай 3. Клонировать, продлить и отменить.
0.
0, 1.
0, 2, 6.
0, 2, 6, 9.
0, 2, 6, 14. Отброшено.
----------------------------------------------- ------------------------------
A [10] = 5. Случай 3. Клонировать, продлить и отменить.
0.
0, 1.
0, 1, 5.
0, 2, 6. Отброшено.
0, 2, 6, 9.
----------------------------------------------- ------------------------------
A [11] = 13. Случай 2. Клонирование и расширение.
0.
0, 1.
0, 1, 5.
0, 2, 6, 9.
0, 2, 6, 9, 13.
----------------------------------------------- ------------------------------
A [12] = 3. Случай 3. Клонировать, продлить и отменить.
0.
0, 1.
0, 1, 3.
0, 1, 5. Отброшено.
0, 2, 6, 9.
0, 2, 6, 9, 13.
----------------------------------------------- ------------------------------
A [13] = 11. Случай 3. Клонировать, протягивать и отбрасывать.
0.
0, 1.
0, 1, 3.
0, 2, 6, 9.
0, 2, 6, 9, 11.
0, 2, 6, 9, 13. Отброшено.
----------------------------------------------- ------------------------------
A [14] = 7. Случай 3. Клонировать, растягивать и отбрасывать.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9. Отброшено.
0, 2, 6, 9, 11.
----------------------------------------------- -----------------------------
A [15] = 15. Случай 2. Клонирование и расширение.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9, 11.
0, 2, 6, 9, 11, 15. < - Список LIS
Кроме того, убедитесь, что мы сохранили условие: "конечный элемент меньшего списка меньше конечных элементов больших списков".
Этот алгоритм называется "Сортировка терпения".
http://en.wikipedia.org/wiki/Patience_sorting
Итак, подберите костюм из колоды карт. Найдите самую длинную увеличивающуюся подпоследовательность карт из перетасованного костюма. Вы никогда не забудете этот подход.
Сложность: O (NlogN)
Источник: http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
Ответ 4
Основная идея алгоритма состоит в том, чтобы сохранить список LIS заданной длины, заканчивающийся наименьшим возможным элементом. Построение такой последовательности
- Найти ближайшую предшественницу в уже известной последней последовательности элементов (скажем, ее длина
k) - Попробуйте добавить текущий элемент к этой последовательности и построить новое лучшее решение для длины
k+1
Поскольку на первом этапе вы выполняете поиск меньшего значения, тогда X [i] новое решение (для k+1) будет иметь последний элемент, а затем более короткую последовательность.
Надеюсь, это поможет.
Ответ 5
i придумал этот
set<int> my_set;
set<int>::iterator it;
vector <int> out;
out.clear();
my_set.clear();
for(int i = 1; i <= n; i++) {
my_set.insert(a[i]);
it = my_set.find(a[i]);
it++;
if(it != my_set.end())
st.erase(it);
else
out.push_back(*it);
}
cout<< out.size();
Ответ 6
Вы не можете понять, потому что код в Википедии неправильный (я твердо верю в это). Это не только неправильно, но переменные имеют плохое имя. Но это позволило мне потратить время, чтобы понять, как это работает: D.
Теперь после того, как я прочитал терпение-сортировать. Я переписал алгоритм. Я также написал исправленный бинарный поиск.
Терпение терпения похоже на вставку
Подобно сортировке вставкой, сортировка терпения находит подходящее место для следующего элемента, выполняя бинарный поиск. Бинарный поиск выполняется на кучах карт, построенных в отсортированном порядке. Позвольте мне назначить переменную для колоды карт (я говорю об игре в карты, потому что терпение - это упрощенная карточная игра).
//! card piles contain pile of cards, nth pile contains n cards.
int top_card_list[n+1];
for(int i = 0; i <= n; i++) {
top_card_list[i] = -1;
}
Теперь список top_card_list содержит верхнюю карту стопки карт высотой n. Сортировка терпения помещает карту в руку поверх самой верхней верхней карты, которая меньше ее (или наоборот). Для дальнейшей сортировки заметок, пожалуйста, обратитесь к странице Википедии для сортировки терпения.
3
* 7 2
-------------------------------------------------------------
Pile of cards above (top card is larger than lower cards)
(note that pile of card represents longest increasing subsequence too !)
Бинарный поиск по стопке карт
Теперь, чтобы найти число при динамическом программировании подпоследовательности с наибольшим увеличением, мы запускаем внутренний цикл O(n).
for(int i = 1; i < n; i++) { // outer loop
for(int j = 0; j < i; j++) { // inner loop
if(arr[i] > arr[j]) {
if(memo_len[i] < (memo_len[j]+1)) {
// relaxation
memo_len[i] = memo_len[j]+1;
result = std::max(result,memo_len[i]);
pred[i] = j;
}
}
}
}
И внутренний цикл находится там, чтобы найти самую верхнюю карту, которая меньше нашей карты в руке.
Но мы знаем, что мы можем сделать это с помощью бинарного поиска! (упражнение: доказать правильность) Таким образом, мы можем сделать это за O(log (number of piles)) времени. Теперь O(number of piles)= O(number of cards) (но количество карт 52, это должно быть O (1) !, просто шучу!). Таким образом, общее приложение выполняется за O(n log n) времени.
Вот исправленный ДП с бинарным поиском.
for(int i = 1; i < n; i++) {
pile_height[i] = 1;
const int j = pile_search(top_card_list, arr, pile_len, arr[i]);
if(arr[i] > arr[j]) {
if(pile_height[i] < (pile_height[j]+1)) {
// relaxation
pile_height[i] = pile_height[j]+1;
result = std::max(result,pile_height[i]);
pile_len = std::max(pile_len,pile_height[i]);
}
}
if(-1 == top_card_list[pile_height[i]] || arr[top_card_list[pile_height[i]]] > arr[i]) {
top_card_list[pile_height[i]] = i; // top card on the pile is now i
}
}
Вот правильный поиск стопки ниже. Это просто бинарный поиск, но он находит индекс верхней карты, который меньше, чем карта в руке.
inline static int pile_search(const int*top_card_list, const vector<int>& arr, int pile_len, int strict_upper_limit) {
int start = 1,bound=pile_len;
while(start < bound) {
if(arr[top_card_list[bound]] < strict_upper_limit) {
return top_card_list[bound];
}
int mid = (start+bound)/2 + ((start+bound)&1);
if(arr[top_card_list[mid]] >= strict_upper_limit) {
// go lower
bound = mid-1;
} else {
start = mid;
}
}
return top_card_list[bound];
}
Обратите внимание, что в отличие от Википедии, он возвращает top_card_list[bound] (мое исправление). Также обратите внимание, где top_card_list[] обновляется в дп. Этот код проверен на граничные случаи. Я надеюсь, что это помогает.
Ответ 7
Есть доказательство здесь https://strncat.github.io/jekyll/update/2019/06/25/longest-increasing-subsequence.html
в принципе невозможно не быть строго возрастающей подпоследовательностью. Доказательство противоречиво. Предположим, что это не так, у нас есть два случая: Случай 1) Существует некоторый элемент M [j], который завершает две подпоследовательности длины j и j + некоторое число. Это невозможно (доказательство в ссылке)
Случай 2) Слегка отличается от случая 1, но довольно похожи рассуждения. Как вы можете иметь наименьшее число и две подпоследовательности двух разных длин? этого не может быть