CEA MAI LUNGĂ SUBSECVENȚĂ ÎN CREȘTERE (LIS) - TECHCODEVIEW.COM

Dată o matrice arr[] de mărime N , sarcina este de a găsi lungimea celei mai lungi subsecvențe crescătoare (LIS), adică cea mai lungă subsecvență posibilă în care elementele subsecvenței sunt sortate în ordine crescătoare.

Cea mai lungă subsecvență în creștere

Exemple:

sortare de selecție

Intrare: arr[] = {3, 10, 2, 1, 20}
Ieșire: 3
Explicaţie: Cea mai lungă succesiune crescătoare este 3, 10, 20

Intrare: arr[] = {50, 3, 10, 7, 40, 80}
Ieșire: 4
Explicaţie: Cea mai lungă succesiune crescătoare este {3, 7, 40, 80}

Intrare: arr[] = {30, 20, 10}
Ieșire: 1
Explicaţie: Cele mai lungi subsecvențe crescătoare sunt {30}, {20} și (10)

Intrare: arr[] = {10, 20, 35, 80}
Ieșire: 4
Explicaţie: Întreaga matrice este sortată

Cea mai lungă secvență de creștere folosind Recursiune :

Ideea de a parcurge matricea de intrare de la stânga la dreapta și de a găsi lungimea celei mai lungi secvențe în creștere (LIS) care se termină cu fiecare element arr[i]. Fie lungimea găsită pentru arr[i] L[i]. La sfârșit, returnăm maximul tuturor valorilor L[i]. Acum apare întrebarea, cum calculăm L[i]? Pentru aceasta, folosim recursiunea, luăm în considerare toate elementele mai mici din stânga lui arr[i], calculăm recursiv valoarea LIS pentru toate elementele mai mici din stânga, luăm maximul tuturor și adăugăm 1 la acesta. Dacă nu există niciun element mai mic în stânga unui element, returnăm 1.

Lăsa L(i) fi lungimea LIS care se termină la index i astfel încât arr[i] este ultimul element al LIS. Atunci, L(i) poate fi scris recursiv ca:

L(i) = 1 + max(L(j) ) unde 0
L(i) = 1, dacă nu există un astfel de j.
Formal, lungimea LIS se termină la index i , este cu 1 mai mare decât lungimea maximă a tuturor LIS care se termină la un anumit index j astfel încât arr[j] Unde j .

Putem vedea că relația de recurență de mai sus urmează substructură optimă proprietate.

Ilustrare:

Urmați ilustrația de mai jos pentru o mai bună înțelegere:

Luați în considerare arr[] = {3, 10, 2, 11}

L(i): denotă LIS de subbary care se termină la poziția „i”

Arborele recursiv

Urmați pașii menționați mai jos pentru a implementa ideea de mai sus:

Creați o funcție recursivă.
Pentru fiecare apel recursiv, Iterați de la i = 1 la poziția curentă și faceți următoarele:
Găsiți lungimea posibilă a celei mai lungi secvențe crescătoare care se termină la poziția curentă dacă secvența anterioară s-a încheiat la i .
Actualizați lungimea maximă posibilă în consecință.
Repetați acest lucru pentru toți indicii și găsiți răspunsul
Mai jos este implementarea abordării recursive:
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; } // Comparați max_ending_here cu // max. Și actualizați // max. general dacă este necesar dacă (*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ți max_ending_here cu // totalul max. Și actualizați valoarea maximă generală dacă este necesar dacă (*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ți max_ending_here cu totalul maxim. Și // actualizați valoarea maximă generală dacă este necesar dacă (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>Piton# 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 cu maximul general. Și # actualizați maximul general dacă este necesar maximum = max(maximum, maxEndingHere) return maxEndingHere def lis(arr): # Pentru a permite accesul variabilei globale maxime globale # Lungimea arr n = len(arr) # Variabila maximă deține rezultatul maximum = 1 # Funcția _lis() stochează rezultatul în maximum _lis(arr, n) return maximum # Program driver pentru a testa funcția de mai sus dacă __name__ == '__main__': arr = [10, 22, 9, 33 , 21, 50, 41, 60] n = len(arr) # Apelul funcției print('Lungimea lis este', lis(arr)) # Acest cod este contribuit de NIKHIL KUMAR SINGH>>>C#max_ending_here) max_ending_here = res + 1; } // Comparați max_ending_here cu maximul general // și actualizați maximul general dacă este necesar dacă (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

>>>  
  Ieșire      Complexitatea timpului:    O(2ⁿ) Complexitatea în timp a acestei abordări recursive este exponențială, deoarece există un caz de subprobleme suprapuse, așa cum este explicat în diagrama arborescentă recursivă de mai sus.  
    Spațiu auxiliar:    O(1). Nu este utilizat spațiu extern pentru stocarea valorilor în afară de spațiul intern al stivei.
inițializator de dicționar c#
 Subsecvența cu cea mai lungă creștere folosind Memorarea :
 Dacă este observată cu atenție, putem vedea că soluția recursivă de mai sus urmează și     subprobleme suprapuse     proprietate, adică aceeași substructură rezolvată din nou și din nou în căi de apel recursive diferite. Putem evita acest lucru folosind abordarea memorizării.
 Putem vedea că fiecare stare poate fi identificată în mod unic folosind doi parametri:
     Index curent    (indică ultimul indice al LIS) și
    Indexul anterior    (indică indexul final al LIS-ului precedent în spatele căruia    arr[i]    este în curs de concatenare).
Mai jos este implementarea abordării de mai sus.
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) { 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 lua = INT_MIN;  if (prev_idx == -1 || a[idx]> a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx][prev_idx + 1] = max(take, notTake); } // Funcție pentru a găsi lungimea // cea mai lungă subsecvență în creștere int longestSubsequence(int n, int a[]) { vector> dp(n + 1, vector (n + 1, -1));  returnează f(0, -1, n, a, dp); } // Program driver pentru a testa funcția de mai sus int main() { int a[] = { 3, 10, 2, 1, 20 };  int n = dimensiunea(a) / dimensiunea(a[0]);  // Apelul funcției 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]) { take = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx][prev_idx + 1] = Math.max(take, notTake);  } // Funcția wrapper pentru _lis() static int lis(int arr[], int n) { // Funcția _lis() își stochează rezultatul în max int dp[][] = new int[n + 1][ n + 1];  for (int row[] : dp) Arrays.fill(row, -1);  returnează f(0, -1, n, arr, dp);  } // Program driver pentru a testa funcțiile de mai sus public static void main(String args[]) { int a[] = { 3, 10, 2, 1, 20 };  int n = a.lungime;  // Apel de funcție System.out.println('Lungimea lis este ' + lis(a, n));  } } // Acest cod este contribuit de Sanskar.>>>Piton
 C# // 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]) { take = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx, prev_idx + 1] = Math.Max(take, notTake);  } // Funcție pentru a găsi lungimea celei mai lungi //secvențe crescătoare.  public static int longestSubsequence(int n, int[] a) { int[, ] dp = new int[n + 1, n + 1];  pentru (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]) { take = 1 + f(idx + 1, idx, n, a, dp);  } return (dp[idx][prev_idx + 1] = Math.max(take, notTake));  } // Funcție pentru a găsi lungimea celei mai lungi //secvențe crescătoare.  function longestSubsequence(n, a) { var dp = Array(n + 1) .fill() .map(() => Array(n + 1).fill(-1));  returnează f(0, -1, n, a, dp);  } /* Program driver pentru a testa funcția de mai sus */ var a = [3, 10, 2, 1, 20];  var n = 5;  console.log('Lungimea lisului este ' + longestSubsequence(n, a));    // Acest cod este contribuit de satwiksuman.>>>  
  Ieșire      Complexitatea timpului:    PE²)  
    Spațiu auxiliar:    PE²)
 Subsecvența cu cea mai lungă creștere folosind Programare dinamică :
 Datorită substructurii optime și a proprietății subproblemei suprapuse, putem folosi și programarea dinamică pentru a rezolva problema. În loc de memorare, putem folosi bucla imbricată pentru a implementa relația recursivă.
 Bucla exterioară va rula de la    i = 1 la N    iar bucla interioară va rula din    j = 0 la i    și folosiți relația de recurență pentru a rezolva problema.
 
Mai jos este implementarea abordării de mai sus:
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>
 Piton # 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 >>>  
  Ieșire      Complexitatea timpului:    PE²) Ca o buclă imbricată este folosită.  
    Spațiu auxiliar:    O(N) Utilizarea oricărei matrice pentru a stoca valorile LIS la fiecare index.
     Notă:    Complexitatea de timp a soluției de programare dinamică (DP) de mai sus este O(n^2), dar există un    O(N* logN) soluție    pentru problema LIS. Nu am discutat aici soluția O(N log N).  
Consultați:     Dimensiunea subsecvenței cu cea mai lungă creștere (N * logN)             pentru abordarea menționată.

TechCodeview

Subsecvența cu cea mai lungă creștere (LIS)

Cea mai lungă secvență de creștere folosind Recursiune :

Subsecvența cu cea mai lungă creștere folosind Memorarea :

Subsecvența cu cea mai lungă creștere folosind Programare dinamică :