OK, je décrirai d’abord la solution la plus simple qui est O (N ^ 2), où N est la taille de la collection. Il existe également une solution O (N log N) que je décrirai également. Regardez ici pour la section Algorithmes efficaces.

Je suppose que les indices du tableau vont de 0 à N – 1. Définissons donc DP[i] comme étant la longueur du LIS (sous-séquence croissante la plus longue) qui se termine à l’élément index i . Pour calculer DP[i] nous examinons tous les indices j < i et vérifions si DP[j] + 1 > DP[i] et le array[j] < array[i] (nous voulons qu'il augmente). Si cela est vrai, nous pouvons mettre à jour l'optimum actuel pour DP[i] . Pour trouver l'optimum global de la masortingce, vous pouvez prendre la valeur maximale de DP[0...N - 1] .

 int maxLength = 1, bestEnd = 0; DP[0] = 1; prev[0] = -1; for (int i = 1; i < N; i++) { DP[i] = 1; prev[i] = -1; for (int j = i - 1; j >= 0; j--) if (DP[j] + 1 > DP[i] && array[j] < array[i]) { DP[i] = DP[j] + 1; prev[i] = j; } if (DP[i] > maxLength) { bestEnd = i; maxLength = DP[i]; } } 

J'utilise le tableau prev pour pouvoir retrouver ultérieurement la séquence réelle, non seulement sa longueur. Revenez récursivement de bestEnd dans une boucle en utilisant prev[bestEnd] . La valeur -1 est un signe à arrêter.

OK, maintenant à la solution plus efficace O(N log N) :

Soit S[pos] défini comme le plus petit entier qui termine une séquence croissante de longueur pos . Maintenant, parcourez chaque entier X du jeu d'entrées et procédez comme suit:

1. Si X > dernier élément dans S , alors ajoutez X à la fin de S Cela signifie que nous avons trouvé un nouveau plus grand LIS .

2. Sinon, trouvez le plus petit élément dans S , qui est >= que X , et changez-le en X Comme S est sortingé à tout moment, l'élément peut être trouvé en utilisant la recherche binary dans log(N) .

Temps d'exécution total - N entiers et une recherche binary pour chacun d'eux - N * log (N) = O (N log N)

Maintenant, faisons un exemple concret:

Collection de nombres entiers: 2 6 3 4 1 2 9 5 8

Pas:

 0. S = {} - Initialize S to the empty set 1. S = {2} - New largest LIS 2. S = {2, 6} - New largest LIS 3. S = {2, 3} - Changed 6 to 3 4. S = {2, 3, 4} - New largest LIS 5. S = {1, 3, 4} - Changed 2 to 1 6. S = {1, 2, 4} - Changed 3 to 2 7. S = {1, 2, 4, 9} - New largest LIS 8. S = {1, 2, 4, 5} - Changed 9 to 5 9. S = {1, 2, 4, 5, 8} - New largest LIS 

La longueur du LIS est donc 5 (la taille de S).

Pour reconstruire le LIS actuel, nous utiliserons à nouveau un tableau parent. Soit parent[i] le prédécesseur de l'élément avec l'index i dans le LIS terminant par l'élément avec l'index i .

Pour simplifier les choses, nous pouvons conserver dans le tableau S , non pas les entiers réels, mais leurs indices (positions) dans l'ensemble. Nous ne gardons pas {1, 2, 4, 5, 8} , mais gardons {4, 5, 3, 7, 8} .

C'est-à-dire entrée [4] = 1 , entrée [5] = 2 , entrée [3] = 4 , entrée [7] = 5 , entrée [8] = 8 .

Si nous mettons à jour correctement le tableau parent, le LIS actuel est:

 input[S[lastElementOfS]], input[parent[S[lastElementOfS]]], input[parent[parent[S[lastElementOfS]]]], ........................................ 

Maintenant à l'important - comment met-on à jour le tableau parent? Il y a deux options:

1. Si X > dernier élément dans S , alors parent[indexX] = indexLastElement . Cela signifie que le parent de l'élément le plus récent est le dernier élément. Nous avons juste ajouté X à la fin de S

2. Sinon, recherchez l'index du plus petit élément dans S , qui est >= que X , et changez-le en X Ici parent[indexX] = S[index - 1] .

L’explication de Petar Minchev a aidé à clarifier les choses pour moi, mais il était difficile pour moi d’parsingr ce que tout était, alors j’ai réalisé une implémentation Python avec des noms de variables trop descriptifs et beaucoup de commentaires. J’ai fait une solution récursive naïve, la solution O (n ^ 2) et la solution O (n log n).

J’espère que cela aide à clarifier les algorithmes!

La solution récursive

 def recursive_solution(remaining_sequence, bigger_than=None): """Finds the longest increasing subsequence of remaining_sequence that is bigger than bigger_than and returns it. This solution is O(2^n).""" # Base case: nothing is remaining. if len(remaining_sequence) == 0: return remaining_sequence # Recursive case 1: exclude the current element and process the remaining. best_sequence = recursive_solution(remaining_sequence[1:], bigger_than) # Recursive case 2: include the current element if it's big enough. first = remaining_sequence[0] if (first > bigger_than) or (bigger_than is None): sequence_with = [first] + recursive_solution(remaining_sequence[1:], first) # Choose whichever of case 1 and case 2 were longer. if len(sequence_with) >= len(best_sequence): best_sequence = sequence_with return best_sequence 

La solution de programmation dynamic O (n ^ 2)

 def dynamic_programming_solution(sequence): """Finds the longest increasing subsequence in sequence using dynamic programming. This solution is O(n^2).""" longest_subsequence_ending_with = [] backreference_for_subsequence_ending_with = [] current_best_end = 0 for curr_elem in range(len(sequence)): # It's always possible to have a subsequence of length 1. longest_subsequence_ending_with.append(1) # If a subsequence is length 1, it doesn't have a backreference. backreference_for_subsequence_ending_with.append(None) for prev_elem in range(curr_elem): subsequence_length_through_prev = (longest_subsequence_ending_with[prev_elem] + 1) # If the prev_elem is smaller than the current elem (so it's increasing) # And if the longest subsequence from prev_elem would yield a better # subsequence for curr_elem. if ((sequence[prev_elem] < sequence[curr_elem]) and (subsequence_length_through_prev > longest_subsequence_ending_with[curr_elem])): # Set the candidate best subsequence at curr_elem to go through prev. longest_subsequence_ending_with[curr_elem] = (subsequence_length_through_prev) backreference_for_subsequence_ending_with[curr_elem] = prev_elem # If the new end is the best, update the best. if (longest_subsequence_ending_with[curr_elem] > longest_subsequence_ending_with[current_best_end]): current_best_end = curr_elem # Output the overall best by following the backreferences. best_subsequence = [] current_backreference = current_best_end while current_backreference is not None: best_subsequence.append(sequence[current_backreference]) current_backreference = (backreference_for_subsequence_ending_with[current_backreference]) best_subsequence.reverse() return best_subsequence 

La solution de programmation dynamic O (n log n)

 def find_smallest_elem_as_big_as(sequence, subsequence, elem): """Returns the index of the smallest element in subsequence as big as sequence[elem]. sequence[elem] must not be larger than every element in subsequence. The elements in subsequence are indices in sequence. Uses binary search.""" low = 0 high = len(subsequence) - 1 while high > low: mid = (high + low) / 2 # If the current element is not as big as elem, throw out the low half of # sequence. if sequence[subsequence[mid]] < sequence[elem]: low = mid + 1 # If the current element is as big as elem, throw out everything bigger, but # keep the current element. else: high = mid return high def optimized_dynamic_programming_solution(sequence): """Finds the longest increasing subsequence in sequence using dynamic programming and binary search (per http://en.wikipedia.org/wiki/Longest_increasing_subsequence). This solution is O(n log n).""" # Both of these lists hold the indices of elements in sequence and not the # elements themselves. # This list will always be sorted. smallest_end_to_subsequence_of_length = [] # This array goes along with sequence (not # smallest_end_to_subsequence_of_length). Following the corresponding element # in this array repeatedly will generate the desired subsequence. parent = [None for _ in sequence] for elem in range(len(sequence)): # We're iterating through sequence in order, so if elem is bigger than the # end of longest current subsequence, we have a new longest increasing # subsequence. if (len(smallest_end_to_subsequence_of_length) == 0 or sequence[elem] > sequence[smallest_end_to_subsequence_of_length[-1]]): # If we are adding the first element, it has no parent. Otherwise, we # need to update the parent to be the previous biggest element. if len(smallest_end_to_subsequence_of_length) > 0: parent[elem] = smallest_end_to_subsequence_of_length[-1] smallest_end_to_subsequence_of_length.append(elem) else: # If we can't make a longer subsequence, we might be able to make a # subsequence of equal size to one of our earlier subsequences with a # smaller ending number (which makes it easier to find a later number that # is increasing). # Thus, we look for the smallest element in # smallest_end_to_subsequence_of_length that is at least as big as elem # and replace it with elem. # This preserves correctness because if there is a subsequence of length n # that ends with a number smaller than elem, we could add elem on to the # end of that subsequence to get a subsequence of length n+1. location_to_replace = find_smallest_elem_as_big_as(sequence, smallest_end_to_subsequence_of_length, elem) smallest_end_to_subsequence_of_length[location_to_replace] = elem # If we're replacing the first element, we don't need to update its parent # because a subsequence of length 1 has no parent. Otherwise, its parent # is the subsequence one shorter, which we just added onto. if location_to_replace != 0: parent[elem] = (smallest_end_to_subsequence_of_length[location_to_replace - 1]) # Generate the longest increasing subsequence by backtracking through parent. curr_parent = smallest_end_to_subsequence_of_length[-1] longest_increasing_subsequence = [] while curr_parent is not None: longest_increasing_subsequence.append(sequence[curr_parent]) curr_parent = parent[curr_parent] longest_increasing_subsequence.reverse() return longest_increasing_subsequence 

À propos de la solution DP, j’ai trouvé surprenant que personne n’ait mentionné le fait que LIS puisse être réduit à LCS . Tout ce que vous avez à faire est de sortinger la copie de la séquence d’origine, de supprimer tous les doublons et d’effectuer un LCS. En pseudocode c’est:

 def LIS(S): T = sort(S) T = removeDuplicates(T) return LCS(S, T) 

Et l’implémentation complète écrite en Go. Vous n’avez pas besoin de maintenir toute la masortingce n ^ 2 DP si vous n’avez pas besoin de reconstruire la solution.

 func lcs(arr1 []int) int { arr2 := make([]int, len(arr1)) for i, v := range arr1 { arr2[i] = v } sort.Ints(arr1) arr3 := []int{} prev := arr1[0] - 1 for _, v := range arr1 { if v != prev { prev = v arr3 = append(arr3, v) } } n1, n2 := len(arr1), len(arr3) M := make([][]int, n2 + 1) e := make([]int, (n1 + 1) * (n2 + 1)) for i := range M { M[i] = e[i * (n1 + 1):(i + 1) * (n1 + 1)] } for i := 1; i <= n2; i++ { for j := 1; j <= n1; j++ { if arr2[j - 1] == arr3[i - 1] { M[i][j] = M[i - 1][j - 1] + 1 } else if M[i - 1][j] > M[i][j - 1] { M[i][j] = M[i - 1][j] } else { M[i][j] = M[i][j - 1] } } } return M[n2][n1] } 

L’implémentation C ++ suivante inclut également du code qui génère la sous- séquence ayant la plus longue augmentation en utilisant un tableau appelé prev .

 std::vector longest_increasing_subsequence (const std::vector& s) { int best_end = 0; int sz = s.size(); if (!sz) return std::vector(); std::vector prev(sz,-1); std::vector memo(sz, 0); int max_length = std::numeric_limits::min(); memo[0] = 1; for ( auto i = 1; i < sz; ++i) { for ( auto j = 0; j < i; ++j) { if ( s[j] < s[i] && memo[i] < memo[j] + 1 ) { memo[i] = memo[j] + 1; prev[i] = j; } } if ( memo[i] > max_length ) { best_end = i; max_length = memo[i]; } } // Code that builds the longest increasing subsequence using "prev" std::vector results; results.reserve(sz); std::stack stk; int current = best_end; while (current != -1) { stk.push(s[current]); current = prev[current]; } while (!stk.empty()) { results.push_back(stk.top()); stk.pop(); } return results; } 

Implémentation sans stack, inversez simplement le vecteur

 #include  #include  #include  std::vector LIS( const std::vector &v ) { auto sz = v.size(); if(!sz) return v; std::vector memo(sz, 0); std::vector prev(sz, -1); memo[0] = 1; int best_end = 0; int max_length = std::numeric_limits::min(); for (auto i = 1; i < sz; ++i) { for ( auto j = 0; j < i ; ++j) { if (s[j] < s[i] && memo[i] < memo[j] + 1) { memo[i] = memo[j] + 1; prev[i] = j; } } if(memo[i] > max_length) { best_end = i; max_length = memo[i]; } } // create results std::vector results; results.reserve(v.size()); auto current = best_end; while (current != -1) { results.push_back(s[current]); current = prev[current]; } std::reverse(results.begin(), results.end()); return results; } 

Voici trois étapes pour évaluer le problème du sharepoint vue de la programmation dynamic:

1. Définition de récurrence: maxLength (i) == 1 + maxLength (j) où 0 tableau [j]
2. Limite du paramètre de récurrence: il pourrait y avoir 0 à i – 1 sous-séquence transmise en tant que paramètre
3. Ordre d’évaluation: comme il augmente sous-séquence, il doit être évalué de 0 à n

Si nous prenons comme exemple la séquence {0, 8, 2, 3, 7, 9}, à l’index:

• [0] nous obtiendrons la sous-séquence {0} comme cas de base
• [1] nous avons 1 nouvelle sous-séquence {0, 8}
• [2] essayant d’évaluer deux nouvelles séquences {0, 8, 2} et {0, 2} en ajoutant un élément à l’index 2 aux sous-séquences existantes – une seule est valide, ajoutant ainsi une troisième séquence possible {0, 2} seulement à la liste des parameters …

Voici le code C ++ 11 qui fonctionne:

 #include  #include  int getLongestIncSub(const std::vector &sequence, size_t index, std::vector> &sub) { if(index == 0) { sub.push_back(std::vector{sequence[0]}); return 1; } size_t longestSubSeq = getLongestIncSub(sequence, index - 1, sub); std::vector> tmpSubSeq; for(std::vector &subSeq : sub) { if(subSeq[subSeq.size() - 1] < sequence[index]) { std::vector newSeq(subSeq); newSeq.push_back(sequence[index]); longestSubSeq = std::max(longestSubSeq, newSeq.size()); tmpSubSeq.push_back(newSeq); } } std::copy(tmpSubSeq.begin(), tmpSubSeq.end(), std::back_insert_iterator>>(sub)); return longestSubSeq; } int getLongestIncSub(const std::vector &sequence) { std::vector> sub; return getLongestIncSub(sequence, sequence.size() - 1, sub); } int main() { std::vector seq{0, 8, 2, 3, 7, 9}; std::cout << getLongestIncSub(seq); return 0; } 

Voici une implémentation Scala de l’algorithme O (n ^ 2):

 object Solve { def longestIncrSubseq[T](xs: List[T])(implicit ord: Ordering[T]) = { xs.foldLeft(List[(Int, List[T])]()) { (sofar, x) => if (sofar.isEmpty) List((1, List(x))) else { val resIfEndsAtCurr = (sofar, xs).zipped map { (tp, y) => val len = tp._1 val seq = tp._2 if (ord.lteq(y, x)) { (len + 1, x :: seq) // reversely recorded to avoid O(n) } else { (1, List(x)) } } sofar :+ resIfEndsAtCurr.maxBy(_._1) } }.maxBy(_._1)._2.reverse } def main(args: Array[Ssortingng]) = { println(longestIncrSubseq(List( 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15))) } } 

Voici une autre implémentation O (n ^ 2) JAVA. Pas de récursivité / mémo pour générer la sous-séquence réelle. Juste un tableau de chaînes qui stocke le LIS réel à chaque étape et un tableau pour stocker la longueur du LIS pour chaque élément. Assez facile Regarde:

 import java.io.BufferedReader; import java.io.InputStreamReader; /** * Created by Shreyans on 4/16/2015 */ class LNG_INC_SUB//Longest Increasing Subsequence { public static void main(Ssortingng[] args) throws Exception { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter Numbers Separated by Spaces to find their LIS\n"); Ssortingng[] s1=br.readLine().split(" "); int n=s1.length; int[] a=new int[n];//Array actual of Numbers Ssortingng []ls=new Ssortingng[n];// Array of Ssortingngs to maintain LIS for every element for(int i=0;i=0;j--) { //First check if number at index j is less than num at i. // Second the length of that DP should be greater than dp[i] // -1 since dp of previous could also be one. So we compare the dp[i] as empty initially if(a[j]dp[i]-1) { dp[i]=dp[j]+1;//Assigning temp length of LIS. There may come along a bigger LIS of a future a[j] x=ls[j];//Assigning temp LIS of a[j]. Will append a[i] later on } } x+=(" "+a[i]); ls[i]=x; if(dp[i]>max) { max=dp[i]; seq=ls[i]; } } System.out.println("Length of LIS is: " + max + "\nThe Sequence is: " + seq); } } 

Code en action: http://ideone.com/sBiOQx

Cela peut être résolu en O (n ^ 2) en utilisant la programmation dynamic. Le code Python pour le même serait comme: –

 def LIS(numlist): LS = [1] for i in range(1, len(numlist)): LS.append(1) for j in range(0, i): if numlist[i] > numlist[j] and LS[i]<=LS[j]: LS[i] = 1 + LS[j] print LS return max(LS) numlist = map(int, raw_input().split(' ')) print LIS(numlist) 

Pour entrée: 5 19 5 81 50 28 29 1 83 23

le résultat serait: [1, 2, 1, 3, 3, 3, 4, 1, 5, 3] 5

Le list_index de la liste de sortie est le list_index de la liste d'entrée. La valeur à un list_index donné dans la liste de sortie indique la longueur de sous-séquence croissante la plus longue pour cet index list_index.

voici l’implémentation de Java O (nlogn)

 import java.util.Scanner; public class LongestIncreasingSeq { private static int binarySearch(int table[],int a,int len){ int end = len-1; int beg = 0; int mid = 0; int result = -1; while(beg <= end){ mid = (end + beg) / 2; if(table[mid] < a){ beg=mid+1; result = mid; }else if(table[mid] == a){ return len-1; }else{ end = mid-1; } } return result; } public static void main(String[] args) { // int[] t = {1, 2, 5,9,16}; // System.out.println(binarySearch(t , 9, 5)); Scanner in = new Scanner(System.in); int size = in.nextInt();//4; int A[] = new int[size]; int table[] = new int[A.length]; int k = 0; while(k A[i]){ table[0] = A[i]; }else if(table[len-1]