PISIN KASVAVA OSASEKVENSSI (LIS)

Annettu joukko arr[] kooltaan N , tehtävänä on löytää pisimmän mahdollisen osasekvenssin (LIS) pituus, eli pisin mahdollinen osasekvenssi, jossa osasarjan elementit lajitellaan kasvavaan järjestykseen.

Pisin kasvava jakso

Esimerkkejä:

Syöte: arr[] = {3, 10, 2, 1, 20}
Lähtö: 3
Selitys: Pisin kasvava osasekvenssi on 3, 10, 20

Syöte: arr[] = {50, 3, 10, 7, 40, 80}
Lähtö: 4
Selitys: Pisin kasvava osasarja on {3, 7, 40, 80}

Syöte: arr[] = {30, 20, 10}
Lähtö: 1
Selitys: Pisin kasvavat osasekvenssit ovat {30}, {20} ja (10)
java-lajittelutaulukko

Syöte: arr[] = {10, 20, 35, 80}
Lähtö: 4
Selitys: Koko joukko on lajiteltu

Pisin kasvava jakso käytössä Rekursio :

Ajatus kulkea syötetaulukon läpi vasemmalta oikealle ja löytää pisimpään kasvavan osasekvenssin (LIS) pituus, joka päättyy jokaiseen elementtiin arr[i]. Olkoon arr[i]:lle löydetty pituus L[i]. Lopussa palautetaan maksimi kaikista L[i]-arvoista. Nyt herää kysymys, kuinka laskemme L[i]? Tätä varten me rekursio, otamme huomioon kaikki pienemmät elementit arr[i]:n vasemmalla puolella, laskemme rekursiivisesti LIS-arvon kaikille vasemmanpuoleisille pienemmille elementeille, otamme kaikista maksimi ja lisäämme siihen 1. Jos elementin vasemmalla puolella ei ole pienempää elementtiä, palautetaan 1.

Antaa L(i) on indeksiin päättyvän LIS:n pituus i siten, että arr[i] on LIS:n viimeinen elementti. Sitten L(i) voidaan kirjoittaa rekursiivisesti seuraavasti:

L(i) = 1 + max(L(j) ) missä 0
L(i) = 1, jos sellaista j:tä ei ole olemassa.
Muodollisesti LIS:n pituus, joka päättyy indeksiin i , on 1 suurempi kuin kaikkien johonkin indeksiin päättyvien LIS:ien pituus j sellasta arr[j] missä j .

Voimme nähdä, että yllä oleva toistuvuussuhde seuraa optimaalinen alusrakenne omaisuutta.

Kuva:

Seuraa alla olevaa kuvaa ymmärtääksesi paremmin:

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

L(i): Tarkoittaa alijärjestelmän LIS:ää, joka päättyy kohtaan 'i'

Rekursiopuu

Toteuta yllä oleva idea noudattamalla alla mainittuja vaiheita:

Luo rekursiivinen funktio.
Toisto jokaiselle rekursiiviselle kutsulle i = 1 nykyiseen paikkaan ja toimi seuraavasti:
Etsi pisimmän kasvavan osajonon mahdollinen pituus, joka päättyy nykyiseen paikkaan, jos edellinen sekvenssi päättyi i .
Päivitä suurin mahdollinen pituus vastaavasti.
Toista tämä kaikille indekseille ja löydä vastaus
Alla on rekursiivisen lähestymistavan toteutus:
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; } // Vertaa max_ending_here // yleiseen maksimiarvoon. Ja päivitä // yleinen enimmäisarvo tarvittaessa, jos (*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; } // Vertaa max_ending_here kokonaisarvoon // max. Ja päivittää yleisen enimmäisarvon tarvittaessa, jos (*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; } // Vertaa max_ending_ here yleiseen max. Ja // päivittää yleisen enimmäisarvon tarvittaessa, jos (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 # Vertaa maxEndingHerea kokonaismaksimiin. Ja # päivitä kokonaismaksimi tarvittaessa maksimi = max(maksimi, maxEndingHere) return maxEndingHere def lis(arr): # Salli globaalin muuttujan pääsyn globaaliin maksimiarvoon # Arr:n pituus n = len(arr) # Maksimimuuttuja pitää tuloksen max = 1 # Funktio _lis() tallentaa tuloksensa maksimiarvoon _lis(arr, n) return maximum # Ohjainohjelma testaamaan yllä olevaa funktiota, jos __name__ == '__main__': arr = [10, 22, 9, 33 , 21, 50, 41, 60] n = len(arr) # Funktiokutsu print('Length of lis is', lis(arr)) # Tämän koodin tarjoaa 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; } // Vertaa max_ending_here yleiseen maksimiarvoon // ja päivitä kokonaismaksimi tarvittaessa jos (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

>>  
  Lähtö      Aika monimutkaisuus:    O(2ⁿ) Tämän rekursiivisen lähestymistavan aikamonimutkaisuus on eksponentiaalinen, koska on olemassa päällekkäisiä aliongelmia, kuten yllä olevassa rekursiivisessa puukaaviossa selitetään.  
    Aputila:    O(1). Arvojen tallentamiseen ei käytetä ulkoista tilaa sisäisen pinotilan lisäksi.
 Pisin kasvava jatkojakso käytössä Memoisointi :
 Huolellisesti huomioituna voimme nähdä, että yllä oleva rekursiivinen ratkaisu seuraa myös     päällekkäisiä aliongelmia     ominaisuus eli sama alirakenne, joka ratkaistaan uudelleen ja uudelleen eri rekursiokutsupoluilla. Voimme välttää tämän käyttämällä memoisointimenetelmää.
 Näemme, että jokainen tila voidaan yksilöidä kahdella parametrilla:
     Nykyinen indeksi    (merkitsee LIS:n viimeistä indeksiä) ja
    Edellinen indeksi    (merkitsee edellisen LIS:n loppuindeksiä, jonka takana on    arr[i]    ketjutetaan).
Alla on edellä mainitun lähestymistavan toteutus.
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][edellinen_idx + 1] != -1) { return dp[idx][edellinen_idx + 1];  } int notTake = 0 + f(idx + 1, edellinen_idx, n, a, dp);  int take = INT_MIN;  if (edellinen_idx == -1 || a[idx]> a[edellinen_idx]) { ota = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx][edellinen_idx + 1] = max(ota, eiOta); } // Funktio löytää // pisimmän kasvavan osajonon pituus int longestSubsequence(int n, int a[]) { vektori> dp(n + 1, vektori (n + 1, -1));  return f(0, -1, n, a, dp); } // Ajuriohjelma testattava yllä oleva funktio int main() { int a[] = { 3, 10, 2, 1, 20 };  int n = koko(a) / koko(a[0]);  // Funktion kutsu<< '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[edellinen_idx]) { ota = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx][edellinen_idx + 1] = Math.max(take, notTake);  } // Kääritty funktio _lis() static int lis(int arr[], int n) { // Funktio _lis() tallentaa tuloksensa max int dp[][] = new int[n + 1][ n + 1];  for (int rivi[] : dp) Arrays.fill(rivi, -1);  return f(0, -1, n, arr, dp);  } // Ohjainohjelma yllä olevien toimintojen testaamiseen public static void main(String args[]) { int a[] = { 3, 10, 2, 1, 20 };  int n = a.pituus;  // Toimintokutsu System.out.println('Lin pituus on ' + lis(a, n));  } } // Tämän koodin on toimittanut 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[edellinen_idx]) { ota = 1 + f(idx + 1, idx, n, a, dp);  } return dp[idx, edellinen_idx + 1] = Math.Max(ota, eiOta);  } // Funktio pisimmän kasvavan // osajonon pituuden löytämiseksi.  julkinen staattinen int pisinSubsequence(int n, int[] a) { int[, ] dp = uusi 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[edellinen_idx]) { ota = 1 + f(idx + 1, idx, n, a, dp);  } return (dp[idx][edellinen_idx + 1] = Math.max(take, notTake));  } // Funktio pisimmän kasvavan // osajonon pituuden löytämiseksi.  function pisinSubsequence(n, a) { var dp = Array(n + 1) .fill() .map(() => Array(n + 1).fill(-1));  return f(0, -1, n, a, dp);  } /* Ohjainohjelma testattava yllä oleva toiminto */ var a = [3, 10, 2, 1, 20];  var n = 5;  console.log('Lisän pituus on ' + longestSubsequence(n, a));    // Tämän koodin on toimittanut satwiksuman.>>  
  Lähtö      Aika monimutkaisuus:    PÄÄLLÄ²)  
    Aputila:    PÄÄLLÄ²)
 Pisin kasvava jatkojakso käytössä Dynaaminen ohjelmointi :
 Optimaalisen alirakenteen ja päällekkäisen aliongelmaominaisuuden ansiosta voimme myös käyttää dynaamista ohjelmointia ongelman ratkaisemiseen. Memoisoinnin sijaan voimme käyttää sisäkkäistä silmukkaa rekursiivisen suhteen toteuttamiseen.
 Ulompi silmukka alkaa    i = 1 - N    ja sisäsilmukka alkaa    j = 0 - i    ja käytä toistuvuussuhdetta ongelman ratkaisemiseen.
 
Alla on yllä olevan lähestymistavan toteutus:
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] ja 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 >>  
  Lähtö      Aika monimutkaisuus:    PÄÄLLÄ²) Sisäkkäisenä silmukana käytetään.  
    Aputila:    O(N) Minkä tahansa taulukon käyttö LIS-arvojen tallentamiseen jokaiseen indeksiin.
     Huomautus:    Yllä olevan Dynamic Programming (DP) -ratkaisun aikamonimutkaisuus on O(n^2), mutta siinä on    O(N*logN)-liuos    LIS-ongelman vuoksi. Emme ole keskustelleet O(N log N) -ratkaisusta tässä.  
Viitata:     Pisin kasvava osasarjan koko (N * logN)             mainitulle lähestymistavalle.

TechCodeview

Pisin kasvava jakso käytössä Rekursio :

Pisin kasvava jatkojakso käytössä Memoisointi :

Pisin kasvava jatkojakso käytössä Dynaaminen ohjelmointi :