самая длинная возрастающая подпоследовательность (O (nlogn))

Question

LIS: wikipedia

Есть одна вещь, которую я не могу понять:

почему X [M [i]] - неубывающая последовательность?

Answer 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;
   }
}

Answer 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;
}

Answer 3

Нам нужно вести списки увеличивающихся последовательностей.

В общем, у нас есть множество активных списков различной длины. Мы добавляем элемент A [i] в ​​эти списки. Мы сканируем списки (для конечных элементов) в порядке убывания их длины. Мы проверим конечные элементы всех списков, чтобы найти список, конечный элемент которого меньше A [i] (минимальное значение).

Наша стратегия определяется следующими условиями,
1. Если A [i] является наименьшим среди всех конечных кандидатов в активные списки, мы запустим новый активный список длиной 1.
2. Если A [i] является наибольшим среди всех конечных кандидатов в активные списки, мы клонируем самый большой активный список и расширим его на A [i].
3. Если A [i] находится между ними, мы найдем список с наибольшим конечным элементом, который меньше, чем A [i]. Клонировать и расширить этот список на A [i]. Мы отбрасываем все остальные списки той же длины, что и этот измененный список.

Обратите внимание, что в любом случае во время построения активных списков выполняется следующее условие.

«конечный элемент меньшего списка меньше конечных элементов больших списков».

Это будет понятно на примере, давайте возьмем пример из вики:
{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.
----------------------------------------------- ------------------------------
[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 List </strong>

Также убедитесь, что мы сохранили условие «конечный элемент меньшего списка меньше конечных элементов больших списков».
Этот алгоритм называется сортировкой терпения.
http://en.wikipedia.org/wiki/Patience_sorting

Итак, выберите костюм из колоды карт. Найдите самую длинную увеличивающуюся последовательность карт из перетасованной масти. Вы никогда не забудете подход.

Сложность: O (NlogN) * ​​1164 *

Источник: http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

Answer 4

Здесь есть доказательство https://strncat.github.io/jekyll/update/2019/06/25/longest-increasing-subsequence.html

в принципе невозможно не быть строго возрастающей подпоследовательностью. Доказательство противоречиво. Предположим, что это не так, у нас есть два случая: Случай 1) Существует некоторый элемент M [j], который завершает две подпоследовательности длины j и j + некоторое число. Это невозможно (доказательство в ссылке)

Случай 2) Слегка отличается от случая 1, но довольно похожи рассуждения. Как вы можете иметь наименьшее число и две подпоследовательности двух разных длин? этого не может быть

Answer 5

Вы не можете понять, потому что код в Википедии неправильный (я твердо верю в это). Это не только неправильно, но переменные имеют плохое имя. Но это позволило мне потратить время, чтобы понять, как это работает: 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) раз.

Вот исправленный DP с бинарным поиском.

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

Answer 6

я придумал это

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();

Answer 7

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

1. Найти непосредственного предшественника в уже известной последовательности последних элементов (скажем, его длина k)
2. Попробуйте добавить текущий элемент в эту последовательность и построить новое лучшее решениедля k+1 длина

Поскольку на первом шаге вы ищете меньшее значение, чем X [i], новое решение (для k+1) будет иметь последний элемент больше короткой последовательности.

Надеюсь, это поможет.