la plus longue sous-séquence croissante (O(nlogn))

Question

LIS:wikipedia

Il y a une chose que je ne comprends pas :

pourquoi X[M[i]] est-elle une suite non décroissante ?

Answer 1

Examinons d'abord l'algorithme 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;
         }
      }
   }
}

L'amélioration se produit au niveau de la deuxième boucle. En fait, vous pouvez améliorer la vitesse en utilisant la recherche binaire. En plus du tableau dp[], nous avons un autre tableau c[], c est assez spécial, c[i] signifie : la valeur minimale du dernier élément de la plus longue séquence croissante dont la longueur est 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

Il s'agit de la solution O(n*lg(n)) de Le guide de l'auto-stoppeur pour les concours de programmation (note : cette implémentation suppose qu'il n'y a pas de doublons dans la liste) :

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;

Pour tenir compte des doublons, on pourrait vérifier, par exemple, si le numéro figure déjà dans la série. Si c'est le cas, on ne tient pas compte du numéro, sinon on continue à utiliser la même méthode que précédemment. Il est également possible d'inverser l'ordre des opérations : d'abord supprimer, puis insérer. Le code ci-dessous met en œuvre ce comportement :

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;

Le deuxième algorithme pourrait être étendu pour trouver la plus longue sous-séquence croissante (LIS) elle-même en maintenant un tableau parent qui contient la position de l'élément précédent de la LIS dans le tableau original.

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

Nous devons tenir à jour des listes de séquences croissantes.

En général, nous disposons d'un ensemble de listes actives de longueur variable. Nous ajoutons un élément A[i] à ces listes. Nous parcourons les listes (à la recherche des éléments finaux) dans l'ordre décroissant de leur longueur. Nous vérifions les éléments finaux de toutes les listes pour trouver une liste dont l'élément final est plus petit que A[i] (valeur plancher).

Notre stratégie est déterminée par les conditions suivantes,
1. Si A[i] est le plus petit parmi tous les candidats finaux des listes actives, nous commencerons une nouvelle liste active de longueur 1.
2. Si A[i] est le plus grand parmi tous les candidats finaux des listes actives, nous clonerons la plus grande liste active et l'allongerons de A[i].
3. Si A[i] se trouve entre les deux, nous trouverons une liste dont l'élément final le plus grand est plus petit que A[i]. Nous clonons et étendons cette liste par A[i]. Nous rejetterons toutes les autres listes de même longueur que cette liste modifiée.

Notez qu'à tout moment de notre construction de listes actives, la condition suivante est maintenue.

"L'élément final d'une liste plus petite est plus petit que les éléments finaux de listes plus grandes.

Cela sera plus clair avec un exemple, prenons l'exemple de wiki :
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

A[0] = 0. Cas 1. Il n'y a pas de liste active, créez-en une.

0. -----------------------------------------------------------------------------
   A[1] = 8. Cas 2. Clonage et extension.

1. 0, 8.
   -----------------------------------------------------------------------------
   A[2] = 4. Cas 3. Cloner, étendre et rejeter.

2. 0, 4.
   0, 8. rejeté
   -----------------------------------------------------------------------------
   A[3] = 12. Cas 2. Cloner et étendre.

3. 0, 4.
   0, 4, 12.
   -----------------------------------------------------------------------------
   A[4] = 2. Cas 3. Cloner, étendre et rejeter.

4. 0, 2.
   0, 4. rejeté.
   0, 4, 12.
   -----------------------------------------------------------------------------
   A[5] = 10. Cas 3. Cloner, étendre et jeter.

5. 0, 2.
   0, 2, 10.
   0, 4, 12. Rejeté.
   -----------------------------------------------------------------------------
   A[6] = 6. Troisième cas de figure. Cloner, étendre et rejeter.

6. 0, 2.
   0, 2, 6.
   0, 2, 10. Rejeté.
   -----------------------------------------------------------------------------
   A[7] = 14. Cas 2. Cloner et étendre.

7. 0, 2.
   0, 2, 6.
   0, 2, 6, 14.
   -----------------------------------------------------------------------------
   A[8] = 1. Cas 3. Cloner, étendre et rejeter.

8. 0, 1.
   0, 2. rejetées.
   0, 2, 6.
   0, 2, 6, 14.
   -----------------------------------------------------------------------------
   A[9] = 9. Cas 3. Cloner, étendre et rejeter.

9. 0, 1.
   0, 2, 6.
   0, 2, 6, 9.
   0, 2, 6, 14. Rejeté.
   -----------------------------------------------------------------------------
   A[10] = 5. Cas 3. Cloner, étendre et jeter.

10. 0, 1.
    0, 1, 5.
    0, 2, 6. Rejeté.
    0, 2, 6, 9.
    -----------------------------------------------------------------------------
    A[11] = 13. Cas 2. Cloner et étendre.

11. 0, 1.
    0, 1, 5.
    0, 2, 6, 9.
    0, 2, 6, 9, 13.
    -----------------------------------------------------------------------------
    A[12] = 3. Cas 3. Cloner, étendre et rejeter.

12. 0, 1.
    0, 1, 3.
    0, 1, 5. rejeté.
    0, 2, 6, 9.
    0, 2, 6, 9, 13.
    -----------------------------------------------------------------------------
    A[13] = 11. Cas 3. Cloner, étendre et rejeter.

13. 0, 1.
    0, 1, 3.
    0, 2, 6, 9.
    0, 2, 6, 9, 11.
    0, 2, 6, 9, 13. Rejeté.
    -----------------------------------------------------------------------------
    A[14] = 7. Cas 3. Cloner, étendre et rejeter.

14. 0, 1.
    0, 1, 3.
    0, 1, 3, 7. 0, 2, 6, 9. Rejeté.
    0, 2, 6, 9, 11.
    ----------------------------------------------------------------------------
    A[15] = 15. Cas 2. Cloner et étendre.

15. 0, 1.
    0, 1, 3.
    0, 1, 3, 7.
    0, 2, 6, 9, 11.
    0, 2, 6, 9, 11, 15. <-- Liste LIS

Assurez-vous également que la condition "l'élément final de la plus petite liste est plus petit que les éléments finaux des plus grandes listes" a été maintenue.
Cet algorithme s'appelle le tri par patience.
http://en.wikipedia.org/wiki/Patience_sorting

Choisissez donc une couleur dans le jeu de cartes. Trouvez la plus longue sous-séquence croissante de cartes de la couleur mélangée. Vous n'oublierez jamais cette approche.

Complexité : O(NlogN)

Fuente: http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

Answer 4

J'ai trouvé ceci

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 5

Vous ne pouvez pas comprendre, parce que le code dans wikipedia est erroné (je le crois fermement). Non seulement il est faux, mais les variables sont mal nommées. Mais cela m'a permis de passer du temps à comprendre comment cela fonctionne :D.

Maintenant que j'ai lu le tri de la patience. J'ai réécrit l'algorithme. J'ai également écrit la recherche binaire corrigée.

Le tri par patience est comme le tri par insertion

Comme le tri par insertion, le tri par patience trouve l'emplacement approprié pour l'élément suivant en effectuant une recherche binaire. La recherche binaire est effectuée sur les piles de cartes construites dans l'ordre trié. Je vais assigner une variable à la pile de cartes (je parle de cartes à jouer car la patience est un jeu de cartes simplifié).

//! 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;
}

Aujourd'hui, le top_card_list contient la carte supérieure de la pile de cartes de hauteur n . Le tri par patience consiste à placer la carte en main sur la carte supérieure la plus haute qui est plus petite qu'elle (ou l'inverse). Pour plus d'informations sur le tri, veuillez vous référer à la page wikipedia sur le tri par patience.

             3
  *   7      2                   
-------------------------------------------------------------
  Pile of cards above (top card is larger than lower cards)
 (note that pile of card represents longest increasing subsequence too !)

Recherche binaire sur une pile de cartes

Maintenant, pour trouver un nombre pendant que nous faisons de la programmation dynamique pour la sous-séquence la plus longue, nous exécutons une boucle interne qui est 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;
            }
        }
    }
 }

Et la boucle intérieure est là pour trouver la carte la plus haute qui est plus petite que la carte que nous avons en main.

Mais nous savons que nous pouvons le faire par recherche binaire ! (exercice : prouver l'exactitude) De cette façon, nous pouvons le faire en O(log (number of piles)) temps. Aujourd'hui O(number of piles) = O(number of cards) (mais le nombre de cartes est de 52, ce devrait être O(1), je plaisante). Ainsi, l'application totale s'exécute en O(n log n) temps.

Voici la version révisée du DP avec recherche binaire.

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

Voici la recherche de pile correcte ci-dessous. Il s'agit simplement d'une recherche binaire, mais elle trouve l'index de la carte supérieure qui est plus petite que la carte en main.

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

Notez que contrairement à wikipedia, il renvoie top_card_list[bound] (ma solution). Remarquez également l'endroit où le top_card_list[] est mis à jour dans le dp. Ce code est testé pour les cas limites. J'espère qu'il vous sera utile.