ILGIAUSIAI DIDĖJANTI SEKA (LIS)

Duotas masyvas arr[] dydžio N , užduotis yra rasti ilgiausios didėjančios posekos (LIS) ilgį, t. y. ilgiausią įmanomą posekos, kurioje posekos elementai rūšiuojami didėjančia tvarka.

Ilgiausiai didėjanti seka

Pavyzdžiai:

Įvestis: arr[] = {3, 10, 2, 1, 20}
Išvestis: 3
Paaiškinimas: Ilgiausia didėjanti seka yra 3, 10, 20

Įvestis: arr[] = {50, 3, 10, 7, 40, 80}
Išvestis: 4
Paaiškinimas: Ilgiausia didėjanti poseka yra {3, 7, 40, 80}

Java

Įvestis: arr[] = {30, 20, 10}
Išvestis: 1
Paaiškinimas: Ilgiausiai didėjančios posekos yra {30}, {20} ir (10)

Įvestis: arr[] = {10, 20, 35, 80}
Išvestis: 4
Paaiškinimas: Visas masyvas surūšiuotas

Ilgiausia didėjanti seka naudojant Rekursija :

Idėja pereiti įvesties masyvą iš kairės į dešinę ir rasti ilgiausios didėjančios sekos (LIS) ilgį, kuris baigiasi kiekvienu elementu arr[i]. Tegul arr[i] rastas ilgis yra L[i]. Pabaigoje grąžiname didžiausią visų L[i] reikšmių skaičių. Dabar kyla klausimas, kaip apskaičiuoti L[i]? Tam mes, rekursija, atsižvelgiame į visus mažesnius elementus kairėje nuo arr[i], rekursyviai apskaičiuojame visų mažesnių elementų LIS reikšmę kairėje, paimame visų didžiausią ir pridedame prie jo 1. Jei elemento kairėje nėra mažesnio elemento, grąžiname 1.

Leisti L(i) yra LIS ilgis, kuris baigiasi indeksu i taip, kad arr[i] būtų paskutinis LIS elementas. Tada L(i) gali būti rekursyviai parašytas taip:
svyruojantis css

L(i) = 1 + max(L(j) ), kur 0
L(i) = 1, jei tokio j nėra.
Formaliai LIS ilgis baigiasi indeksu i , yra 1 didesnis už maksimalų visų LIS ilgį, kuris baigiasi tam tikru indeksu j toks kad arr[j] kur j .

Matome, kad aukščiau pateiktas pasikartojimo ryšys seka optimali substruktūra nuosavybė.

Iliustracija:
leksikografinė tvarka

Norėdami geriau suprasti, vadovaukitės toliau pateikta iliustracija:

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

L(i): žymi pogrupio LIS, kuris baigiasi „i“ padėtyje

Rekursijos medis

Atlikite toliau nurodytus veiksmus, kad įgyvendintumėte aukščiau pateiktą idėją:

Sukurkite rekursinę funkciją.
Kiekvienam rekursiniam skambučiui kartoti iš i = 1 į dabartinę padėtį ir atlikite šiuos veiksmus:
Raskite galimą ilgiausios didėjančios posekos, kuri baigiasi dabartine padėtimi, ilgį, jei ankstesnė seka baigėsi i .
Atitinkamai atnaujinkite didžiausią galimą ilgį.
Pakartokite tai visiems indeksams ir raskite atsakymą
Žemiau pateikiamas rekursinio metodo įgyvendinimas:
pandos kuria duomenų rėmelį
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; } // Palyginkite max_ending_here su // bendru maks. Jei reikia, atnaujinkite // bendrą maks. jei (*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; } // Palyginkite max_ending_here su bendra // maks. Jei reikia, atnaujinkite bendrą maksimalų skaičių, jei (*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; } // Palyginkite max_ending_čia su bendru maks. Ir // atnaujinkite bendrą maksimalų dydį, jei reikia, jei (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 # Palyginkite maxEndingHere su bendru maksimumu. Ir # atnaujinkite bendrą maksimalų skaičių, jei reikia maksimalus = max(maksimalus, maxEndingHere) return maxEndingHere def lis(arr): # Kad būtų galima pasiekti visuotinį kintamąjį global maximum # Length of arr n = len(arr) # Maksimalus kintamasis turi rezultatą maximum = 1 # Funkcija _lis() išsaugo savo rezultatą maksimaliai _lis(arr, n) grąžina maksimumą # Tvarkyklės programa, kad patikrintų aukščiau pateiktą funkciją, jei __name__ == '__main__': arr = [10, 22, 9, 33 , 21, 50, 41, 60] n = len(arr) # Funkcijos iškvietimas print('Length of lis is', lis(arr)) # Šį kodą sukūrė NIKHIL KUMAR SINGH>>C#max_ending_here) max_ending_here = res + 1; } // Palyginkite max_ending_here su bendru max // ir atnaujinkite bendrą maksimalų dydį, jei reikia (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

>>  
  Išvestis      Laiko sudėtingumas:    O(2ⁿ) Šio rekursinio metodo sudėtingumas laike yra eksponentinis, nes yra sutampančių subproblemų atvejis, kaip paaiškinta anksčiau pateiktoje rekursyvaus medžio diagramoje.  
    Pagalbinė erdvė:    O(1). Vertėms saugoti nenaudojama jokia išorinė erdvė, išskyrus vidinę kamino erdvę.
 Ilgiausiai didėjanti seka naudojant Atmintinė :
 Jei atidžiai pastebėsime, pamatysime, kad aukščiau pateiktas rekursinis sprendimas taip pat seka     persidengiančios subproblemos     savybė, ty ta pati postruktūra, vėl ir vėl išsprendžiama skirtinguose rekursijos iškvietimo keliuose. Mes galime to išvengti naudodami atmintinės metodą.
 Matome, kad kiekviena būsena gali būti unikaliai identifikuojama naudojant du parametrus:
     Dabartinis indeksas    (žymi paskutinę LIS indeksą) ir
    Ankstesnis indeksas    (žymi ankstesnio LIS pabaigos indeksą, už kurio yra    arr[i]    yra jungiamas).
Žemiau pateikiamas pirmiau minėto metodo įgyvendinimas.
dvejetainis medis inorder traversal
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][ankstesnis_idx + 1] != -1) { return dp[idx][ankstesnis_idx + 1];  } int notTake = 0 + f(idx + 1, ankstesnis_idx, n, a, dp);  int take = INT_MIN;  if (ankstesnis_idx == -1 || a[idx]> a[ankstesnis_idx]) { imti = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx][ankstesnis_idx + 1] = max(imti, neimti); } // Funkcija rasti // ilgiausiai didėjančios posekos ilgį int longestSubsequence(int n, int a[]) { vektorius> dp(n + 1, vektorius (n + 1, -1));  return f(0, -1, n, a, dp); } // Tvarkyklės programa, skirta patikrinti aukščiau pateiktą funkciją int main() { int a[] = { 3, 10, 2, 1, 20 };  int n = dydis(a) / dydis(a[0]);  // Funkcijos iškvietimas<< '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[ankstesnis_idx]) { imti = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx][ankstesnis_idx + 1] = Math.max(take, notTake);  } // _lis() įvyniojimo funkcija static int lis(int arr[], int n) { // Funkcija _lis() išsaugo savo rezultatą max int dp[][] = new int[n + 1][ n + 1];  for (int row[] : dp) Arrays.fill(row, -1);  return f(0, -1, n, arr, dp);  } // Tvarkyklės programa aukščiau pateiktoms funkcijoms išbandyti public static void main(String args[]) { int a[] = { 3, 10, 2, 1, 20 };  int n = a.ilgis;  // Funkcijos iškvietimas System.out.println('Lis ilgis yra ' + lis(a, n));  } } // Šį kodą pateikė Sanskar.>>Python
 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[ankstesnis_idx]) { imti = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx, ankstesnis_idx + 1] = Math.Max(imti, neimti);  } // Funkcija ilgiausiai didėjančios // posekos ilgiui rasti.  public static int longestSubsequence(int n, int[] a) { int[, ] dp = new int[n + 1, n + 1];  už (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[ankstesnis_idx]) { imti = 1 + f(idx + 1, idx, n, a, dp);  } return (dp[idx][prev_idx + 1] = Math.max(take, notTake));  } // Funkcija ilgiausiai didėjančios // posekos ilgiui rasti.  function longestSubsequence(n, a) { var dp = Masyvas(n + 1) .fill() .map(() => Masyvas(n + 1).fill(-1));  return f(0, -1, n, a, dp);  } /* Tvarkyklės programa, skirta patikrinti aukščiau esančią funkciją */ var a = [3, 10, 2, 1, 20];  var n = 5;  console.log('Length of lis yra ' + longestSubsequence(n, a));    // Šį kodą sukūrė satwiksuman.>>  
  Išvestis      Laiko sudėtingumas:    O (N²)  
    Pagalbinė erdvė:    O (N²)
 Ilgiausiai didėjanti seka naudojant Dinaminis programavimas :
 Dėl optimalios substruktūros ir sutampančios subproblemos savybės, mes taip pat galime naudoti dinaminį programavimą, kad išspręstume problemą. Vietoj atmintinės galime naudoti įdėtą kilpą rekursiniam ryšiui įgyvendinti.
 Išorinė kilpa veiks nuo    i = 1 iki N    ir vidinė kilpa bėgs nuo    j = 0 iki i    ir naudokite pasikartojimo ryšį problemai išspręsti.
 
Žemiau pateikiamas pirmiau minėto metodo įgyvendinimas:
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] ir 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 >>  
  Išvestis      Laiko sudėtingumas:    O (N²) Kaip naudojama įdėta kilpa.  
    Pagalbinė erdvė:    O(N) Bet kurio masyvo naudojimas LIS reikšmėms saugoti kiekviename indekse.
     Pastaba:    Aukščiau pateikto dinaminio programavimo (DP) sprendimo laiko sudėtingumas yra O(n^2), tačiau yra    O(N* logN) tirpalas    dėl LIS problemos. O (N log N) sprendimo čia neaptarėme.  
Žiūrėti:     Ilgiausiai didėjančios sekos dydis (N * logN)             už minėtą požiūrį.

TechCodeview

Ilgiausia didėjanti seka naudojant Rekursija :

Ilgiausiai didėjanti seka naudojant Atmintinė :

Ilgiausiai didėjanti seka naudojant Dinaminis programavimas :