Trouver la plus longue séquence croissante

Question

On vous donne une séquence de nombres et vous devez trouver la plus longue sous-séquence croissante à partir de l'entrée donnée (pas nécessairement continue).

J'ai trouvé le lien vers cette( Sous-séquence croissante la plus longue sur Wikipédia ) mais nécessitent plus d'explications.

Si quelqu'un pouvait m'aider à comprendre l'implémentation O(n log n), ce serait vraiment utile. Si vous pouviez expliquer l'algo avec un exemple, ce serait vraiment apprécié.

J'ai vu les autres posts également et ce que je n'ai pas compris c'est : L = 0 pour i = 1, 2, ... n : recherche binaire de la plus grande valeur positive j ≤ L telle que X[M[j]] < X[i] (ou fixer j = 0 si une telle valeur n'existe pas). dans l'énoncé ci-dessus, d'où commencer la recherche binaire ? comment initialiser M[], X[] ?

Answer 1

Un problème plus simple consiste à trouver la longueur de la plus longue sous-séquence croissante. Vous pouvez vous concentrer sur la compréhension de ce problème en premier lieu. La seule différence de l'algorithme est qu'il n'utilise pas la fonction P le tableau.

x est l'entrée d'une séquence, elle peut donc être initialisée comme : x = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

m garde la trace de la meilleure sous-séquence de chaque longueur trouvé jusqu'à présent. La meilleure est celle dont la valeur finale est la plus petite (ce qui permet d'ajouter un plus grand nombre de valeurs après elle). La longueur et la valeur finale sont les seules données à stocker pour chaque sous-séquence.

Chaque élément de m représente une sous-séquence. Pour m[j] ,

• j est la longueur de la sous-séquence.
• m[j] est l'indice (en x ) du dernier élément de la sous-séquence.
• donc, x[m[j]] est la valeur du dernier élément de la sous-séquence.

L est la longueur de la plus longue sous-séquence trouvée jusqu'à présent. La première L valeurs de m sont valides, les autres ne sont pas initialisés. m peut commencer avec le premier élément étant 0, le reste non initialisé. L augmente au fur et à mesure de l'exécution de l'algorithme, de même que le nombre de valeurs initialisées de m .

Voici un exemple d'exécution. x[i] et m à la fin de chaque itération est donnée (mais les valeurs de la séquence sont utilisées à la place des index).

La recherche dans chaque itération est de trouver où placer x[i] . Elle doit être aussi à droite que possible (pour obtenir la séquence la plus longue) et être supérieure à la valeur située à sa gauche (pour qu'il s'agisse d'une séquence croissante).

 0:  m = [0, 0]        - ([0] is a subsequence of length 1.)
 8:  m = [0, 0, 8]     - (8 can be added after [0] to get a sequence of length 2.)
 4:  m = [0, 0, 4]     - (4 is better than 8. This can be added after [0] instead.)
 12: m = [0, 0, 4, 12] - (12 can be added after [...4])
 2:  m = [0, 0, 2, 12] - (2 can be added after [0] instead of 4.)
 10: m = [0, 0, 2, 10]
 6:  m = [0, 0, 2, 6]
 14: m = [0, 0, 2, 6, 14]
 1:  m = [0, 0, 1, 6, 14]
 9:  m = [0, 0, 1, 6, 9]
 5:  m = [0, 0, 1, 5, 9]
 13: m = [0, 0, 1, 5, 9, 13]
 3:  m = [0, 0, 1, 3, 9, 13]
 11: m = [0, 0, 1, 3, 9, 11]
 7:  m = [0, 0, 1, 3, 7, 11]
 15: m = [0, 0, 1, 3, 7, 11, 15]

Nous savons maintenant qu'il existe une sous-séquence de longueur 6, se terminant par 15. Les valeurs réelles de la sous-séquence peuvent être trouvées en les stockant dans le fichier P pendant la boucle.

Récupération de la meilleure sous-séquence :

P stocke l'élément précédent dans la sous-séquence la plus longue (en tant qu'indice de x), pour chaque nombre, et est mis à jour au fur et à mesure que l'algorithme avance. Par exemple, lorsque nous traitons 8, nous savons qu'il vient après 0, donc nous stockons le fait que 8 est après 0 dans P . Vous pouvez travailler à rebours à partir du dernier chiffre, comme une liste chaînée, pour obtenir la séquence complète.

Ainsi, pour chaque nombre, nous connaissons le nombre qui le précède. Pour trouver la sous-séquence se terminant par 7, on regarde P et voir ça :

7 is after 3
3 is after 1
1 is after 0

On a donc la sous-séquence [0, 1, 3, 7].

Les sous-séquences se terminant par 7 ou 15 partagent certains chiffres :

15 is after 11
11 is after 9
9 is after 6
6 is after 2
2 is after 0

Nous avons donc les sous-séquences [0, 2, 6, 9, 11], et [0, 2, 6, 9, 11, 15] (la plus longue sous-séquence croissante).

Answer 2

L'une des meilleures explications à ce problème est donnée par le site du MIT. http://people.csail.mit.edu/bdean/6.046/dp/

J'espère que cela éclaircira tous vos doutes.

Answer 3

basé sur la réponse de FJB, implémentation java :

public class Lis {

private static int[] findLis(int[] arr) {
    int[] is = new int[arr.length];
    int index = 0;
    is[0] = index;

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[is[index]]) {
            for (int j = 0; j <= index; j++) {
                if (arr[i] < arr[is[j]]) {
                    is[j] = i;
                    break;
                }
            }
        } else if (arr[i] == arr[is[index]]) {

        } else {
            is[++index] = i;
        }
    }

    int[] lis = new int[index + 1];
    lis[index] = arr[is[index]];

    for (int i = index - 1; i >= 0; i--) {
        if (is[i] < is[i + 1]) {
            lis[i] = arr[is[i]];
        } else {
            for (int j = is[i + 1] - 1; j >= 0; j--) {
                if (arr[j] > arr[is[i]] && arr[j] < arr[is[i + 1]]) {
                    lis[i] = arr[j];
                    is[i] = j;
                    break;
                }
            }
        }
    }

    return lis;
}

public static void main(String[] args) {
    int[] arr = new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11,
            7, 15 };
    for (int i : findLis(arr)) {
        System.out.print(i + "-");
    }
    System.out.println();

    arr = new int[] { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
    for (int i : findLis(arr)) {
        System.out.print(i + "-");
    }
    System.out.println();
}

}

Answer 4

Voici l'implémentation de la sous-séquence croissante la plus longue en O(NLogN) :

// search for the index which can be replaced by the X. as the index can't be
//0 or end (because if 0 then replace in the findLIS() and if it's greater than the 
//current maximum the just append)of the array "result" so most of the boundary 
//conditions are not required.
public static int search(int[] result, int p, int r, int x)
{
    if(p > r) return -1;
    int q = (p+r)/2;
    if(result[q] < x && result[q+1]>x)
    {
        return q+1;
    }
    else if(result[q] > x)
    {
        return search(result, p, q, x);
    }
    else
    {
        return search(result, q+1, r, x);
    }
}
    public static int findLIS(int[] a)
    {
        int[] result = new int[a.length];
        result[0] = a[0];
        int index = 0;
        for(int i=1; i<a.length; i++)
        {
            int no = a[i];
            if(no < result[0]) // replacing the min number
            {
                result[0] = no;
            }
            else if(no > result[index])//if the number is bigger then the current big then append
            {
                result[++index] = no;
            }
            else
            {
                int c = search(result, 0, index, no);
                result[c] = no;
            }
        }
        return index+1;
    }

Answer 5

Sur la base de la réponse de @fgb, j'ai implémenté l'algorithme en utilisant c++ pour trouver la plus longue sous-séquence strictement croissante. J'espère que cela vous sera utile.

M[i] est l'indice du dernier élément de la séquence dont la longueur est i, P[i] est l'indice de l'élément précédent de i dans la séquence, qui est utilisé pour imprimer la séquence entière.

doTest() est utilisé pour exécuter le cas de test simple : {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

#include <vector>
using std::vector;
int LIS(const vector<int> &v) {
  int size = v.size(), max_len = 1;
  // M[i] is the index of the last element of the sequence whose length is i
  int *M = new int[size];
  // P[i] is the index of the previous element of i in the sequence, which is used to print the whole sequence
  int *P = new int[size];
  M[0] = 0; P[0] = -1;
  for (int i = 1; i < size; ++i) {
    if (v[i] > v[M[max_len - 1]]) {
      M[max_len] = i;
      P[i] = M[max_len - 1];
      ++max_len;
      continue;
    }
    // Find the position to insert i using binary search
    int lo = 0, hi = max_len - 1;
    while (lo <= hi) {
      int mid = lo + ((hi - lo) >> 1);
      if (v[i] < v[M[mid]]) {
        hi = mid - 1;
      } else if (v[i] > v[M[mid]]) {
        lo = mid + 1;
      } else {
        lo = mid;
        break;
      }
    }
    P[i] = P[M[lo]];  // Modify the previous pointer
    M[lo] = i;  
  }
  // Print the whole subsequence
  int i = M[max_len - 1];
  while (i >= 0) {
    printf("%d ", v[i]);
    i = P[i];
  }
  printf("\n");
  delete[] M, delete[] P;
  return max_len;
}
void doTest() {
  int data[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
  vector<int> v;
  v.insert(v.end(), data, data + sizeof(data) / sizeof(int));
  LIS(v);
}