SUBSEQÜÈNCIA CREIXENT MÉS LLARGA (LIS)

Donada una matriu arr[] de mida N , la tasca és trobar la longitud de la subseqüència creixent més llarga (LIS), és a dir, la subseqüència més llarga possible en què els elements de la subseqüència s'ordenen en ordre creixent.

Subseqüència creixent més llarga

Exemples:

Entrada: arr[] = {3, 10, 2, 1, 20}
Sortida: 3
Explicació: La subseqüència creixent més llarga és 3, 10, 20

Entrada: arr[] = {50, 3, 10, 7, 40, 80}
Sortida: 4
Explicació: La subseqüència creixent més llarga és {3, 7, 40, 80}

Entrada: arr[] = {30, 20, 10}
Sortida: 1
Explicació: Les subseqüències creixents més llargues són {30}, {20} i (10)

Entrada: arr[] = {10, 20, 35, 80}
Sortida: 4
Explicació: Tota la matriu està ordenada

Seqüència creixent més llarga utilitzant Recursió :

La idea és recórrer la matriu d'entrada d'esquerra a dreta i trobar la longitud de la subseqüència creixent més llarga (LIS) que acaba amb cada element arr[i]. Sigui la longitud trobada per a arr[i] L[i]. Al final tornem el màxim de tots els valors L[i]. Ara sorgeix la pregunta, com calculem L[i]? Per a això, fem recursivitat, considerem tots els elements més petits a l'esquerra d'arr[i], calculem recursivament el valor LIS per a tots els elements més petits de l'esquerra, agafem el màxim de tots i hi afegim 1. Si no hi ha cap element més petit a l'esquerra d'un element, retornem 1.

Deixar L(i) ser la longitud del LIS que acaba a l'índex i de manera que arr[i] és l'últim element del LIS. Aleshores, L(i) es pot escriure de manera recursiva com:

L(i) = 1 + max(L(j) ) on 0
L(i) = 1, si no existeix tal j.
Formalment, la durada del LIS acaba a l'índex i , és 1 més gran que el màxim de longituds de tots els LIS que acaben en algun índex j de tal manera que arr[j] on j .

Podem veure que la relació de recurrència anterior segueix la subestructura òptima propietat.

Il·lustració:

Seguiu la il·lustració següent per a una millor comprensió:

Considereu arr[] = {3, 10, 2, 11}

L(i): indica LIS de subbarray que acaba a la posició 'i'

Arbre de recursivitat

Seguiu els passos esmentats a continuació per implementar la idea anterior:

Crea una funció recursiva.
Per a cada trucada recursiva, itereu des de i = 1 a la posició actual i feu el següent:
Trobeu la longitud possible de la subseqüència creixent més llarga que acaba a la posició actual si la seqüència anterior va acabar a i .
Actualitzeu la longitud màxima possible en conseqüència.
Repetiu això per a tots els índexs i trobeu la resposta
A continuació es mostra la implementació de l'enfocament recursiu:
llista de matrius ordenada
C++// A Naive C++ recursive implementation // of LIS problem #include using namespace std; // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element // arr[n-1]. // We use max_ending_here for this purpose // 2) Overall maximum as the LIS may end // with an element before arr[n-1] max_ref // is used this purpose. // The value of LIS of full array of size // n is stored in *max_ref which is // our final result int _lis(int arr[], int n, int* max_ref) { // Base case if (n == 1) return 1; // 'max_ending_here' is length of // LIS ending with arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with // arr[0], arr[1] ... arr[n-2]. If // arr[i-1] is smaller than arr[n-1], // and max ending with arr[n-1] needs // to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i - 1] < arr[n - 1] && res + 1>max_ending_here) max_ending_here = res + 1; } // Compareu max_ending_here amb el // max. I actualitzeu el // màxim global si cal si (*max_ref< max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending // with arr[n-1] return max_ending_here; } // The wrapper function for _lis() int lis(int arr[], int n) { // The max variable holds the result int max = 1; // The function _lis() stores its // result in max _lis(arr, n, &max); // Returns max return max; } // Driver program to test above function int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << 'Length of lis is ' << lis(arr, n); return 0; }>C// A Naive C recursive implementation // of LIS problem #include #include // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element arr[n-1]. // We use max_ending_here for this purpose // 2) Overall maximum as the LIS may end with // an element before arr[n-1] max_ref is // used this purpose. // The value of LIS of full array of size n // is stored in *max_ref which is our final result int _lis(int arr[], int n, int* max_ref) { // Base case if (n == 1) return 1; // 'max_ending_here' is length of LIS // ending with arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with arr[0], // arr[1] ... arr[n-2]. If arr[i-1] is smaller // than arr[n-1], and max ending with arr[n-1] // needs to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i - 1] < arr[n - 1] && res + 1>max_ending_here) max_ending_here = res + 1; } // Compara max_ending_here amb el // max. I actualitzeu el màxim global si cal si (*max_ref< max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() int lis(int arr[], int n) { // The max variable holds the result int max = 1; // The function _lis() stores its result in max _lis(arr, n, &max); // returns max return max; } // Driver program to test above function int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call printf('Length of lis is %d', lis(arr, n)); return 0; }>Java// A Naive Java Program for LIS Implementation import java.io.*; import java.util.*; class LIS { // Stores the LIS static int max_ref; // To make use of recursive calls, this function must // return two things: 1) Length of LIS ending with // element arr[n-1]. We use max_ending_here for this // purpose 2) Overall maximum as the LIS may end with an // element before arr[n-1] max_ref is used this purpose. // The value of LIS of full array of size n is stored in // *max_ref which is our final result static int _lis(int arr[], int n) { // Base case if (n == 1) return 1; // 'max_ending_here' is length of LIS ending with // arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with arr[0], // arr[1] ... arr[n-2]. If arr[i-1] is smaller // than arr[n-1], and max ending with arr[n-1] needs // to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i); if (arr[i - 1] < arr[n - 1] && res + 1>max_ending_here) max_ending_here = res + 1; } // Compara max_ending_here amb el màxim total. I // actualitzeu el màxim global si cal si (max_ref< max_ending_here) max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() static int lis(int arr[], int n) { // The max variable holds the result max_ref = 1; // The function _lis() stores its result in max _lis(arr, n); // Returns max return max_ref; } // Driver program to test above functions public static void main(String args[]) { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.length; // Function call System.out.println('Length of lis is ' + lis(arr, n)); } } // This code is contributed by Rajat Mishra>Python# A naive Python implementation of LIS problem # Global variable to store the maximum global maximum # To make use of recursive calls, this function must return # two things: # 1) Length of LIS ending with element arr[n-1]. We use # max_ending_here for this purpose # 2) Overall maximum as the LIS may end with an element # before arr[n-1] max_ref is used this purpose. # The value of LIS of full array of size n is stored in # *max_ref which is our final result def _lis(arr, n): # To allow the access of global variable global maximum # Base Case if n == 1: return 1 # maxEndingHere is the length of LIS ending with arr[n-1] maxEndingHere = 1 # Recursively get all LIS ending with # arr[0], arr[1]..arr[n-2] # If arr[i-1] is smaller than arr[n-1], and # max ending with arr[n-1] needs to be updated, # then update it for i in range(1, n): res = _lis(arr, i) if arr[i-1] < arr[n-1] and res+1>maxEndingHere: maxEndingHere = res + 1 # Compara maxEndingHere amb el màxim general. I # actualitzeu el màxim global si cal màxim = max(maximum, maxEndingHere) return maxEndingHere def lis(arr): # Per permetre l'accés a la variable global màxim global # Longitud de arr n = len(arr) # La variable màxima conté el resultat màxim = 1 # La funció _lis() emmagatzema el seu resultat al màxim _lis(arr, n) retorn màxim # Programa controlador per provar la funció anterior si __name__ == '__main__': arr = [10, 22, 9, 33 , 21, 50, 41, 60] n = len(arr) # Crida a la funció print('La longitud de lis és', lis(arr)) # Aquest codi és aportat per NIKHIL KUMAR SINGH>>>C#max_ending_here) max_ending_here = res + 1; } // Compareu max_ending_here amb el màxim general // i actualitzeu el màxim global si cal si (max_ref< max_ending_here) max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() static int lis(int[] arr, int n) { // The max variable holds the result max_ref = 1; // The function _lis() stores its result in max _lis(arr, n); // Returns max return max_ref; } // Driver program to test above functions public static void Main() { int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.Length; // Function call Console.Write('Length of lis is ' + lis(arr, n) + ' '); } }>Javascript>
Sortida
Length of lis is 5>

Complexitat temporal: O (2ⁿ) La complexitat temporal d'aquest enfocament recursiu és exponencial, ja que hi ha un cas de subproblemes superposats com s'explica al diagrama d'arbre recursiu anterior.
Espai auxiliar: O(1). No s'utilitza cap espai extern per emmagatzemar valors a part de l'espai intern de la pila.

Subseqüència creixent més llarga utilitzant Memoització :

Si observem amb cura, podem veure que la solució recursiva anterior també segueix el subproblemes superposats propietat, és a dir, la mateixa subestructura es resol una i altra vegada en diferents camins de crida de recursivitat. Això ho podem evitar utilitzant l'enfocament de la memoització.

Podem veure que cada estat es pot identificar de manera única mitjançant dos paràmetres:

Índex actual (indica l'últim índex de la LIS) i
Índex anterior (indica l'índex final de la LIS anterior darrere del qual el arr[i] s'està concatenant).
A continuació es mostra la implementació de l'enfocament anterior.
C++// C++ code of memoization approach for LIS #include using namespace std; // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element // arr[n-1]. // We use max_ending_here for this purpose // Overall maximum as the LIS may end with // an element before arr[n-1] max_ref is // used this purpose. // The value of LIS of full array of size // n is stored in *max_ref which is // our final result int f(int idx, int prev_idx, int n, int a[], vector>& dp) { if (idx == n) { retorna 0; } if (dp[idx][prev_idx + 1] != -1) { return dp[idx][prev_idx + 1]; } int notTake = 0 + f(idx + 1, prev_idx, n, a, dp); int presa = INT_MIN; if (prev_idx == -1 || a[idx]> a[prev_idx]) { pren = 1 + f(idx + 1, idx, n, a, dp); } return dp[idx][prev_idx + 1] = màx(agafar, no prendre); } // Funció per trobar la longitud de // la subseqüència creixent més llarga int longestSubsequence(int n, int a[]) { vector> dp(n + 1, vector (n + 1, -1)); retornar f(0, -1, n, a, dp); } // Programa de controlador per provar la funció anterior int main() { int a[] = { 3, 10, 2, 1, 20 }; int n = grandària de (a) / grandària de (a[0]); // Crida a la funció cout<< 'Length of lis is ' << longestSubsequence(n, a); return 0; }>Java// A Memoization Java Program for LIS Implementation import java.lang.*; import java.util.Arrays; class LIS { // To make use of recursive calls, this function must // return two things: 1) Length of LIS ending with // element arr[n-1]. We use max_ending_here for this // purpose 2) Overall maximum as the LIS may end with an // element before arr[n-1] max_ref is used this purpose. // The value of LIS of full array of size n is stored in // *max_ref which is our final result static int f(int idx, int prev_idx, int n, int a[], int[][] dp) { if (idx == n) { return 0; } if (dp[idx][prev_idx + 1] != -1) { return dp[idx][prev_idx + 1]; } int notTake = 0 + f(idx + 1, prev_idx, n, a, dp); int take = Integer.MIN_VALUE; if (prev_idx == -1 || a[idx]>a[prev_idx]) { pren = 1 + f(idx + 1, idx, n, a, dp); } return dp[idx][prev_idx + 1] = Math.max(agafar, no prendre); } // La funció d'embolcall per a _lis() static int lis(int arr[], int n) { // La funció _lis() emmagatzema el seu resultat a max int dp[][] = new int[n + 1][ n + 1]; for (int fila[] : dp) Arrays.fill(fila, -1); retornar f(0, -1, n, arr, dp); } // Programa de controlador per provar les funcions anteriors public static void main(String args[]) { int a[] = { 3, 10, 2, 1, 20 }; int n = a.longitud; // Crida a la funció System.out.println('La longitud de lis és ' + lis(a, n)); } } // Aquest codi és aportat per Sanskar.>>>PythonC#// C# approach to implementation the memoization approach using System; class GFG { // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element arr[n-1]. // We use max_ending_here for this purpose // 2) Overall maximum as the LIS may end with // an element before arr[n-1] max_ref is // used this purpose. // The value of LIS of full array of size n // is stored in *max_ref which is our final result public static int INT_MIN = -2147483648; public static int f(int idx, int prev_idx, int n, int[] a, int[, ] dp) { if (idx == n) { return 0; } if (dp[idx, prev_idx + 1] != -1) { return dp[idx, prev_idx + 1]; } int notTake = 0 + f(idx + 1, prev_idx, n, a, dp); int take = INT_MIN; if (prev_idx == -1 || a[idx]>a[prev_idx]) { pren = 1 + f(idx + 1, idx, n, a, dp); } return dp[idx, prev_idx + 1] = Math.Max(agafar, no prendre); } // Funció per trobar la longitud de la subseqüència creixent // més llarga. public static int longestSubsequence(int n, int[] a) { int[, ] dp = new int[n + 1, n + 1]; per (int i = 0; i< n + 1; i++) { for (int j = 0; j < n + 1; j++) { dp[i, j] = -1; } } return f(0, -1, n, a, dp); } // Driver code static void Main() { int[] a = { 3, 10, 2, 1, 20 }; int n = a.Length; Console.WriteLine('Length of lis is ' + longestSubsequence(n, a)); } } // The code is contributed by Nidhi goel.>Javascript

/* A Naive Javascript recursive implementation  of LIS problem */  /* To make use of recursive calls, this  function must return two things:  1) Length of LIS ending with element arr[n-1].  We use max_ending_here for this purpose  2) Overall maximum as the LIS may end with  an element before arr[n-1] max_ref is  used this purpose.  The value of LIS of full array of size n  is stored in *max_ref which is our final result  */  function f(idx, prev_idx, n, a, dp) {  if (idx == n) {  return 0;  }  if (dp[idx][prev_idx + 1] != -1) {  return dp[idx][prev_idx + 1];  }  var notTake = 0 + f(idx + 1, prev_idx, n, a, dp);  var take = Number.MIN_VALUE;  if (prev_idx == -1 || a[idx]>a[prev_idx]) { pren = 1 + f(idx + 1, idx, n, a, dp);  } retorn (dp[idx][prev_idx + 1] = Math.max(agafar, no prendre));  } // Funció per trobar la longitud de la subseqüència creixent // més llarga.  function longestSubsequence(n, a) { var dp = Array(n + 1) .fill() .map(() => Array(n + 1).fill(-1));  retornar f(0, -1, n, a, dp);  } /* Programa de controlador per provar la funció anterior */ var a = [3, 10, 2, 1, 20];  var n = 5;  console.log('La longitud del lis és ' + subseqüència més llarga(n, a));    // Aquest codi és aportat per satwiksuman.>>>  
  Sortida  Length of lis is 3>
      Complexitat temporal:    O(N²)  
    Espai auxiliar:    O(N²)
 Subseqüència creixent més llarga utilitzant Programació dinàmica :
 A causa de la subestructura òptima i la propietat del subproblema superposada, també podem utilitzar la programació dinàmica per resoldre el problema. En lloc de la memorització, podem utilitzar el bucle imbricat per implementar la relació recursiva.
 El bucle exterior s'executarà des de    i = 1 a N    i el bucle interior sortirà des de    j = 0 a i    i utilitzar la relació de recurrència per resoldre el problema.
 
A continuació es mostra la implementació de l'enfocament anterior:
C++ // Dynamic Programming C++ implementation // of LIS problem #include  using namespace std; // lis() returns the length of the longest // increasing subsequence in arr[] of size n int lis(int arr[], int n) {  int lis[n];  lis[0] = 1;  // Compute optimized LIS values in  // bottom up manner  for (int i = 1; i < n; i++) {  lis[i] = 1;  for (int j = 0; j < i; j++)  if (arr[i]>arr[j] && lis[i]< lis[j] + 1)  lis[i] = lis[j] + 1;  }  // Return maximum value in lis[]  return *max_element(lis, lis + n); } // Driver program to test above function int main() {  int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function call  printf('Length of lis is %d
', lis(arr, n));  return 0; }>
 Java // Dynamic Programming Java implementation // of LIS problem import java.lang.*; class LIS {  // lis() returns the length of the longest  // increasing subsequence in arr[] of size n  static int lis(int arr[], int n)  {  int lis[] = new int[n];  int i, j, max = 0;  // Initialize LIS values for all indexes  for (i = 0; i < n; i++)  lis[i] = 1;  // Compute optimized LIS values in  // bottom up manner  for (i = 1; i < n; i++)  for (j = 0; j < i; j++)  if (arr[i]>arr[j] && lis[i]< lis[j] + 1)  lis[i] = lis[j] + 1;  // Pick maximum of all LIS values  for (i = 0; i < n; i++)  if (max < lis[i])  max = lis[i];  return max;  }  // Driver code  public static void main(String args[])  {  int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };  int n = arr.length;  // Function call  System.out.println('Length of lis is '  + lis(arr, n));  } } // This code is contributed by Rajat Mishra>
 Python # Dynamic programming Python implementation # of LIS problem # lis returns length of the longest # increasing subsequence in arr of size n def lis(arr): n = len(arr) # Declare the list (array) for LIS and # initialize LIS values for all indexes lis = [1]*n # Compute optimized LIS values in bottom up manner for i in range(1, n): for j in range(0, i): if arr[i]>arr[j] i lis[i]< lis[j] + 1: lis[i] = lis[j]+1 # Initialize maximum to 0 to get # the maximum of all LIS maximum = 0 # Pick maximum of all LIS values for i in range(n): maximum = max(maximum, lis[i]) return maximum # Driver program to test above function if __name__ == '__main__': arr = [10, 22, 9, 33, 21, 50, 41, 60] print('Length of lis is', lis(arr)) # This code is contributed by Nikhil Kumar Singh>
 C# // Dynamic Programming C# implementation of LIS problem using System; class LIS {  // lis() returns the length of the longest increasing  // subsequence in arr[] of size n  static int lis(int[] arr, int n)  {  int[] lis = new int[n];  int i, j, max = 0;  // Initialize LIS values for all indexes  for (i = 0; i < n; i++)  lis[i] = 1;  // Compute optimized LIS values in bottom up manner  for (i = 1; i < n; i++)  for (j = 0; j < i; j++)  if (arr[i]>arr[j] && lis[i]< lis[j] + 1)  lis[i] = lis[j] + 1;  // Pick maximum of all LIS values  for (i = 0; i < n; i++)  if (max < lis[i])  max = lis[i];  return max;  }  // Driver code  public static void Main()  {  int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 };  int n = arr.Length;  // Function call  Console.WriteLine('Length of lis is '  + lis(arr, n));  } } // This code is contributed by Ryuga>
 Javascript >
   
  Sortida      Complexitat temporal:    O(N²) Com que s'utilitza un bucle imbricat.  
    Espai auxiliar:    O(N) Ús de qualsevol matriu per emmagatzemar valors LIS a cada índex.
     Nota:    La complexitat temporal de la solució de programació dinàmica (DP) anterior és O(n^2), però hi ha un    solució O(N* logN).    pel problema LIS. No hem parlat aquí de la solució O(N log N).  
Consulta:     Mida de la subseqüència creixent més llarga (N * logN)             per l'enfocament esmentat.

TechCodeview

Seqüència creixent més llarga utilitzant Recursió :

Subseqüència creixent més llarga utilitzant Memoització :

Subseqüència creixent més llarga utilitzant Programació dinàmica :