Trouver la longueur de la plus grande séquence croissante

Question

Qu'est-ce qu'un algorithme rapide pour trouver la longueur de la plus grande séquence croissante monotone dans un tableau d'entiers.

Answer 1

De Wikipedia: Longest increasing subsequence (O (n log n))

L = 0 
for i = 1, 2, ... n: 
    binary search for the largest positive j ≤ L such that X[M[j]] < X[i] (or set j = 0 if no such value exists) 
    P[i] = M[j] 
    if j == L or X[i] < X[M[j+1]]: 
     M[j+1] = i 
     L = max(L, j+1) 

Answer 2

Je ne sais pas ce que vous entendez par l'algorithme, mais voici une idée.

Si le tableau est trié par défaut (c'est-à-dire lorsque la création d'une valeur de tableau est terminée à la fin du fait qu'il s'agit d'une séquence croissante), récupérez la dernière valeur du tableau.

Si ce n'est pas le cas, créez une nouvelle variable et faites une boucle dans le tableau en affectant la valeur courante à la boucle si elle est plus grande que celle stockée dans la variable temporaire.

Answer 3

Comme le suggère Mehrdad, LIS est au moins proche de ce dont vous avez besoin. Ceci est implémenté le plus efficacement en utilisant programmation dynamique/memoization. Si vous êtes intéressé par des choses comme ça, je vous recommande de la tête sur TopCoder

Answer 4

vous pouvez utiliser la programmation dynamique pour résoudre cette solution problème.Le pour ce problème en utilisant la programmation dynamique est ici:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg