VISILGĀKĀ PIEAUGOŠĀ SECĪBA (LIS)

Dots masīvs arr[] izmēra N , uzdevums ir atrast garākās pieaugošās apakšsecības (LIS) garumu, t.i., garāko iespējamo apakšsecību, kurā apakšsecības elementi ir sakārtoti augošā secībā.

Visilgākā pieaugošā secība

Piemēri:

Ievade: arr[] = {3, 10, 2, 1, 20}
Izvade: 3
Paskaidrojums: Visilgākā pieaugošā apakšsecība ir 3, 10, 20

Ievade: arr[] = {50, 3, 10, 7, 40, 80}
Izvade: 4
Paskaidrojums: Garākā pieaugošā apakšsecība ir {3, 7, 40, 80}

Ievade: arr[] = {30, 20, 10}
Izvade: 1
Paskaidrojums: Visilgāk augošās apakšsecības ir {30}, {20} un (10)

Ievade: arr[] = {10, 20, 35, 80}
Izvade: 4
Paskaidrojums: Viss masīvs ir sakārtots

Garākā pieaugošā secība, izmantojot Rekursija :

Ideja šķērsot ievades masīvu no kreisās puses uz labo un atrast garākās pieaugošās apakšsekvences (LIS) garumu, kas beidzas ar katru elementu arr[i]. Lai arr[i] atrastais garums ir L[i]. Beigās mēs atgriežam maksimālo no visām L[i] vērtībām. Tagad rodas jautājums, kā mēs aprēķinām L[i]? Šim nolūkam mēs, rekursija, apsveram visus mazākos elementus pa kreisi no arr[i], rekursīvi aprēķinām LIS vērtību visiem mazākajiem elementiem kreisajā pusē, ņemam maksimālo no visiem un pievienojam tam 1. Ja elementa kreisajā pusē nav mazāka elementa, mēs atgriežam 1.

Ļaujiet L(i) ir LIS garums, kas beidzas ar indeksu i tā, ka arr[i] ir pēdējais LIS elements. Tad L(i) var rekursīvi uzrakstīt šādi:

L(i) = 1 + max(L(j) ), kur 0
L(i) = 1, ja tāda j nepastāv.
Formāli LIS garums, kas beidzas ar indeksu i , ir par 1 lielāks nekā visu LIS, kas beidzas ar kādu indeksu, maksimālo garumu j tāds, ka arr[j] kur j .

Mēs redzam, ka iepriekš minētā atkārtošanās attiecība seko optimāla apakšstruktūra īpašums.

Ilustrācija:

Izpildiet tālāk sniegto ilustrāciju, lai labāk izprastu:
kā pārvērst int par java virkni

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

L(i): apzīmē apakšgrupas LIS, kas beidzas pozīcijā “i”

Rekursijas koks

Lai īstenotu iepriekš minēto ideju, veiciet tālāk minētās darbības.

Izveidojiet rekursīvu funkciju.
Katram rekursīvajam izsaukumam atkārtojiet no i = 1 uz pašreizējo pozīciju un rīkojieties šādi:
Atrodiet iespējamo garumu augošajai apakšsecībai, kas beidzas pašreizējā pozīcijā, ja iepriekšējā secība beidzās plkst i .
Attiecīgi atjauniniet maksimālo iespējamo garumu.
Atkārtojiet to visiem rādītājiem un atrodiet atbildi
Tālāk ir sniegta rekursīvās pieejas ieviešana:
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; } // Salīdziniet max_ending_here ar // kopējo maks. Ja nepieciešams, atjauniniet // kopējo maksimālo vērtību, ja (*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; } // Salīdziniet max_ending_here ar kopējo // maks. Ja nepieciešams, atjauniniet kopējo maksimālo vērtību, ja (*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; } // Salīdziniet max_ending_here ar kopējo maks. Un // atjauniniet kopējo maksimālo vērtību, ja nepieciešams, ja (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 # Salīdziniet maxEndingHere ar kopējo maksimumu. Un # atjauniniet kopējo maksimumu, ja nepieciešams maksimums = max(maksimums, maxEndingHere) return maxEndingHere def lis(arr): # Lai atļautu piekļuvi globālajam mainīgajam globālajam maksimumam # Arr garums n = len(arr) # Maksimālais mainīgais satur rezultātu maximum = 1 # Funkcija _lis() saglabā rezultātu maksimumā _lis(arr, n) atgriež maksimumu # Draiveris programma, lai pārbaudītu iepriekš minēto funkciju, ja __name__ == '__main__': arr = [10, 22, 9, 33 , 21, 50, 41, 60] n = len(arr) # Funkcijas izsaukuma drukāšana('Length of lis is', lis(arr)) # Šo kodu ir sagatavojis NIKHIL KUMAR SINGH>C#using System; // A Naive C# Program for LIS Implementation 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; } // Salīdziniet max_ending_here ar kopējo max // un atjauniniet kopējo maksimālo vērtību, ja nepieciešams (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

>>  
  Izvade      Laika sarežģītība:    O(2ⁿ) Šīs rekursīvās pieejas laika sarežģītība ir eksponenciāla, jo pastāv apakšproblēmu pārklāšanās gadījums, kā paskaidrots iepriekš redzamajā rekursīvā koka diagrammā.  
    Palīgtelpa:    O(1). Vērtību glabāšanai netiek izmantota ārēja telpa, izņemot iekšējo steka telpu.
 Visilgākā pieaugošā secība, izmantojot Memoizācija :
 Uzmanīgi pamanot, mēs varam redzēt, ka iepriekš minētais rekursīvais risinājums arī seko     apakšproblēmas, kas pārklājas     īpašība, t.i., viena un tā pati apakšstruktūra, kas atkal un atkal tiek atrisināta dažādos rekursijas izsaukuma ceļos. Mēs varam no tā izvairīties, izmantojot memoizācijas pieeju.
 Mēs redzam, ka katru stāvokli var unikāli identificēt, izmantojot divus parametrus:
     Pašreizējais indekss    (apzīmē LIS pēdējo indeksu) un
    Iepriekšējais rādītājs    (apzīmē iepriekšējās LIS beigu indeksu, aiz kura ir    arr[i]    tiek sasaistīts).
Zemāk ir aprakstīta iepriekš minētās pieejas īstenošana.
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][iepriekšējais_idx + 1] != -1) { return dp[idx][iepriekšējais_idx + 1];  } int notTake = 0 + f(idx + 1, prev_idx, n, a, dp);  int take = INT_MIN;  if (iepriekšējais_idx == -1 || a[idx]> a[iepriekšējais_idx]) {ņem = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx][iepriekšējais_idx + 1] = max(ņemt, neņemt); } // Funkcija, lai atrastu // visilgāk augošās apakšsecības garumu int garākāSubsequence(int n, int a[]) { vektors> dp(n + 1, vektors (n + 1, -1));  return f(0, -1, n, a, dp); } // Draivera programma, lai pārbaudītu iepriekš minēto funkciju int main() { int a[] = { 3, 10, 2, 1, 20 };  int n = izmērs(a) / izmērs(a[0]);  // Funkcijas izsaukums<< '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[iepriekšējais_idx]) {ņem = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx][iepriekšējais_idx + 1] = Math.max(ņemt, neņemt);  } // Funkcija _lis() iesaiņojuma funkcija static int lis(int arr[], int n) { // Funkcija _lis() saglabā rezultātu max int dp[][] = new int[n + 1][ n + 1];  for (int row[] : dp) Arrays.fill(rinda, -1);  return f(0, -1, n, arr, dp);  } // Draivera programma, lai pārbaudītu iepriekš minētās funkcijas public static void main(String args[]) { int a[] = { 3, 10, 2, 1, 20 };  int n = a.garums;  // Funkcijas izsaukums System.out.println('Lisa garums ir ' + lis(a, n));  } } // Šo kodu ir sagatavojis 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[iepriekšējais_idx]) {ņem = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx, prev_idx + 1] = Math.Max(ņemt, neņemt);  } // Funkcija, lai atrastu garākās pieaugošās // apakšsecības garumu.  publisks statisks int garākaisApakšsecība(int n, int[] a) { int[, ] dp = jauns int[n + 1, n + 1];  for (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[iepriekšējais_idx]) {ņem = 1 + f(idx + 1, idx, n, a, dp);  } return (dp[idx][iepriekšējais_idx + 1] = Math.max(take, notTake));  } // Funkcija, lai atrastu garākās pieaugošās // apakšsecības garumu.  function garākāSubsequence(n, a) { var dp = Array(n + 1) .fill() .map(() => Array(n + 1).fill(-1));  return f(0, -1, n, a, dp);  } /* Draivera programma, lai pārbaudītu iepriekš minēto funkciju */ var a = [3, 10, 2, 1, 20];  var n = 5;  console.log('Length of lis ir ' + garākāSubsequence(n, a));    // Šo kodu ir sagatavojis satwiksuman.>>  
  Izvade      Laika sarežģītība:    O(N²)  
    Palīgtelpa:    O(N²)
 Visilgāk augošā secība, izmantojot Dinamiskā programmēšana :
 Optimālas apakšstruktūras un pārklājošās apakšproblēmas īpašības dēļ problēmas risināšanai varam izmantot arī dinamisko programmēšanu. Memoizācijas vietā mēs varam izmantot ligzdoto cilpu, lai ieviestu rekursīvo relāciju.
 Ārējā cilpa darbosies no    i = 1 līdz N    un iekšējā cilpa darbosies no    j = 0 līdz i    un izmantojiet atkārtošanās saistību, lai atrisinātu problēmu.
 
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.
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] un 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 >>  
  Izvade      Laika sarežģītība:    O(N²) Kā tiek izmantota ligzdota cilpa.  
    Palīgtelpa:    O(N) Jebkura masīva izmantošana, lai saglabātu LIS vērtības katrā indeksā.
     Piezīme:    Iepriekš minētā dinamiskās programmēšanas (DP) risinājuma laika sarežģītība ir O(n^2), taču ir    O(N* logN) risinājums    LIS problēmai. Mēs šeit neesam apsprieduši O (N log N) risinājumu.  
Atsaukties:     Visilgāk augošās apakšsecības lielums (N * logN)             par minēto pieeju.

TechCodeview

Garākā pieaugošā secība, izmantojot Rekursija :

Visilgākā pieaugošā secība, izmantojot Memoizācija :

Visilgāk augošā secība, izmantojot Dinamiskā programmēšana :