logo

TechCodeview

Langste afwisselende deelreeks

Een reeks {X1 X2 .. Xn} is een afwisselende reeks als de elementen ervan voldoen aan een van de volgende relaties: 

  X1< X2 >X3< X4 >X5< …. xn or 
  X1 > X2< X3 >X4< X5 >…. xn

Voorbeelden:



Invoer: arr[] = {1 5 4}
Uitgang: 3
Uitleg: De hele arrays hebben de vorm x1< x2 >x3 

Invoer: arr[] = {10 22 9 33 49 50 31 60}
Uitgang: 6
Uitleg: De deelreeksen {10 22 9 33 31 60} of
{10 22 9 49 31 60} of {10 22 9 50 31 60}
zijn de langste deelreeks met lengte 6

Aanbevolen praktijk Langste afwisselende deelreeks Probeer het!

Opmerking: Dit probleem is een uitbreiding van de langst toenemende deelreeksprobleem maar vergt meer denkwerk om hierin de optimale onderbouweigenschap te vinden

Langste afwisselende deelreeks met behulp van dynamische programmering :

Om het probleem op te lossen, volgt u het onderstaande idee:

We zullen dit probleem oplossen met behulp van de dynamische programmeermethode, omdat deze een optimale substructuur en overlappende subproblemen heeft

regressietesten bij het testen van software

Volg de onderstaande stappen om het probleem op te lossen:

  • Stel dat A een array met lengte N krijgt 
  • We definiëren een 2D-array las[n][2] zodanig dat las[i][0] de langste afwisselende deelreeks bevat die eindigt op index i en dat het laatste element groter is dan het vorige element 
  • las[i][1] bevat de langste afwisselende deelreeks die eindigt op index i en het laatste element is kleiner dan het vorige element, dan hebben we de volgende herhalingsrelatie daartussen  

las[i][0] = Lengte van de langste afwisselende deelreeks 
                  eindigend op index i en het laatste element is groter
                  dan het vorige element

de[ik][1] = Lengte van de langste afwisselende deelreeks 
                  eindigend bij index i en het laatste element is kleiner
                  dan het vorige element

Recursieve formulering:

   las[i][0] = max (las[i][0] las[j][1] + 1); 
                  voor iedereen j< i and A[j] < A[i] 

   las[i][1] = max (las[i][1] las[j][0] + 1); 
                 voor iedereen j< i and A[j] >EEN[ik]

hoofdmethode java
  • De eerste herhalingsrelatie is gebaseerd op het feit dat als we ons op positie i bevinden en dit element groter moet zijn dan het vorige element, dan zullen we, om deze reeks (tot i) groter te maken, proberen een element j te kiezen (< i) such that A[j] < A[i] i.e. A[j] can become A[i]’s previous element and las[j][1] + 1 is bigger than las[i][0] then we will update las[i][0]. 
  • Onthoud dat we las[j][1] + 1 en niet las[j][0] + 1 hebben gekozen om aan de alternatieve eigenschap te voldoen, omdat in las[j][0] het laatste element groter is dan het vorige en A[i] groter is dan A[j], wat de afwisselende eigenschap zal verbreken als we updaten. Dus bovenstaande feit leidt de eerste herhalingsrelatie af. Een soortgelijk argument kan ook voor de tweede herhalingsrelatie worden aangevoerd. 

Hieronder vindt u de implementatie van de bovenstaande aanpak:

C++ 
// C++ program to find longest alternating // subsequence in an array #include    using namespace std; // Function to return max of two numbers int max(int a int b) { return (a > b) ? a : b; } // Function to return longest alternating // subsequence length int zzis(int arr[] int n) {  /*las[i][0] = Length of the longest  alternating subsequence ending at  index i and last element is greater  than its previous element  las[i][1] = Length of the longest  alternating subsequence ending  at index i and last element is  smaller than its previous element */  int las[n][2];  // Initialize all values from 1  for (int i = 0; i < n; i++)  las[i][0] = las[i][1] = 1;  // Initialize result  int res = 1;  // Compute values in bottom up manner  for (int i = 1; i < n; i++) {  // Consider all elements as  // previous of arr[i]  for (int j = 0; j < i; j++) {  // If arr[i] is greater then  // check with las[j][1]  if (arr[j] < arr[i]  && las[i][0] < las[j][1] + 1)  las[i][0] = las[j][1] + 1;  // If arr[i] is smaller then  // check with las[j][0]  if (arr[j] > arr[i]  && las[i][1] < las[j][0] + 1)  las[i][1] = las[j][0] + 1;  }  // Pick maximum of both values at index i  if (res < max(las[i][0] las[i][1]))  res = max(las[i][0] las[i][1]);  }  return res; } // Driver code int main() {  int arr[] = { 10 22 9 33 49 50 31 60 };  int n = sizeof(arr) / sizeof(arr[0]);  cout << 'Length of Longest alternating '  << 'subsequence is ' << zzis(arr n);  return 0; } // This code is contributed by shivanisinghss2110
C 
// C program to find longest alternating subsequence in // an array #include  #include  // function to return max of two numbers int max(int a int b) { return (a > b) ? a : b; } // Function to return longest alternating subsequence length int zzis(int arr[] int n) {  /*las[i][0] = Length of the longest alternating  subsequence ending at index i and last element is  greater than its previous element las[i][1] = Length of  the longest alternating subsequence ending at index i  and last element is smaller than its previous element  */  int las[n][2];  /* Initialize all values from 1 */  for (int i = 0; i < n; i++)  las[i][0] = las[i][1] = 1;  int res = 1; // Initialize result  /* Compute values in bottom up manner */  for (int i = 1; i < n; i++) {  // Consider all elements as previous of arr[i]  for (int j = 0; j < i; j++) {  // If arr[i] is greater then check with  // las[j][1]  if (arr[j] < arr[i]  && las[i][0] < las[j][1] + 1)  las[i][0] = las[j][1] + 1;  // If arr[i] is smaller then check with  // las[j][0]  if (arr[j] > arr[i]  && las[i][1] < las[j][0] + 1)  las[i][1] = las[j][0] + 1;  }  /* Pick maximum of both values at index i */  if (res < max(las[i][0] las[i][1]))  res = max(las[i][0] las[i][1]);  }  return res; } /* Driver code */ int main() {  int arr[] = { 10 22 9 33 49 50 31 60 };  int n = sizeof(arr) / sizeof(arr[0]);  printf(  'Length of Longest alternating subsequence is %dn'  zzis(arr n));  return 0; }
Java 
// Java program to find longest // alternating subsequence in an array import java.io.*; class GFG {  // Function to return longest  // alternating subsequence length  static int zzis(int arr[] int n)  {  /*las[i][0] = Length of the longest  alternating subsequence ending at  index i and last element is  greater than its previous element  las[i][1] = Length of the longest  alternating subsequence ending at  index i and last element is  smaller than its previous  element */  int las[][] = new int[n][2];  /* Initialize all values from 1 */  for (int i = 0; i < n; i++)  las[i][0] = las[i][1] = 1;  int res = 1; // Initialize result  /* Compute values in bottom up manner */  for (int i = 1; i < n; i++) {  // Consider all elements as  // previous of arr[i]  for (int j = 0; j < i; j++) {  // If arr[i] is greater then  // check with las[j][1]  if (arr[j] < arr[i]  && las[i][0] < las[j][1] + 1)  las[i][0] = las[j][1] + 1;  // If arr[i] is smaller then  // check with las[j][0]  if (arr[j] > arr[i]  && las[i][1] < las[j][0] + 1)  las[i][1] = las[j][0] + 1;  }  /* Pick maximum of both values at  index i */  if (res < Math.max(las[i][0] las[i][1]))  res = Math.max(las[i][0] las[i][1]);  }  return res;  }  /* Driver code*/  public static void main(String[] args)  {  int arr[] = { 10 22 9 33 49 50 31 60 };  int n = arr.length;  System.out.println('Length of Longest '  + 'alternating subsequence is '  + zzis(arr n));  } } // This code is contributed by Prerna Saini
Python3 
# Python3 program to find longest # alternating subsequence in an array # Function to return max of two numbers def Max(a b): if a > b: return a else: return b # Function to return longest alternating # subsequence length def zzis(arr n):  '''las[i][0] = Length of the longest   alternating subsequence ending at  index i and last element is greater  than its previous element  las[i][1] = Length of the longest   alternating subsequence ending   at index i and last element is  smaller than its previous element''' las = [[0 for i in range(2)] for j in range(n)] # Initialize all values from 1 for i in range(n): las[i][0] las[i][1] = 1 1 # Initialize result res = 1 # Compute values in bottom up manner for i in range(1 n): # Consider all elements as # previous of arr[i] for j in range(0 i): # If arr[i] is greater then # check with las[j][1] if (arr[j] < arr[i] and las[i][0] < las[j][1] + 1): las[i][0] = las[j][1] + 1 # If arr[i] is smaller then # check with las[j][0] if(arr[j] > arr[i] and las[i][1] < las[j][0] + 1): las[i][1] = las[j][0] + 1 # Pick maximum of both values at index i if (res < max(las[i][0] las[i][1])): res = max(las[i][0] las[i][1]) return res # Driver Code arr = [10 22 9 33 49 50 31 60] n = len(arr) print('Length of Longest alternating subsequence is' zzis(arr n)) # This code is contributed by divyesh072019
C# 
// C# program to find longest // alternating subsequence // in an array using System; class GFG {  // Function to return longest  // alternating subsequence length  static int zzis(int[] arr int n)  {  /*las[i][0] = Length of the  longest alternating subsequence  ending at index i and last  element is greater than its  previous element  las[i][1] = Length of the longest  alternating subsequence ending at  index i and last element is  smaller than its previous  element */  int[ ] las = new int[n 2];  /* Initialize all values from 1 */  for (int i = 0; i < n; i++)  las[i 0] = las[i 1] = 1;  // Initialize result  int res = 1;  /* Compute values in  bottom up manner */  for (int i = 1; i < n; i++) {  // Consider all elements as  // previous of arr[i]  for (int j = 0; j < i; j++) {  // If arr[i] is greater then  // check with las[j][1]  if (arr[j] < arr[i]  && las[i 0] < las[j 1] + 1)  las[i 0] = las[j 1] + 1;  // If arr[i] is smaller then  // check with las[j][0]  if (arr[j] > arr[i]  && las[i 1] < las[j 0] + 1)  las[i 1] = las[j 0] + 1;  }  /* Pick maximum of both  values at index i */  if (res < Math.Max(las[i 0] las[i 1]))  res = Math.Max(las[i 0] las[i 1]);  }  return res;  }  // Driver Code  public static void Main()  {  int[] arr = { 10 22 9 33 49 50 31 60 };  int n = arr.Length;  Console.WriteLine('Length of Longest '  + 'alternating subsequence is '  + zzis(arr n));  } } // This code is contributed by anuj_67.
PHP 
 // PHP program to find longest  // alternating subsequence in  // an array // Function to return longest // alternating subsequence length function zzis($arr $n) { /*las[i][0] = Length of the   longest alternating subsequence   ending at index i and last element   is greater than its previous element  las[i][1] = Length of the longest   alternating subsequence ending at   index i and last element is   smaller than its previous element */ $las = array(array()); /* Initialize all values from 1 */ for ( $i = 0; $i < $n; $i++) $las[$i][0] = $las[$i][1] = 1; $res = 1; // Initialize result /* Compute values in  bottom up manner */ for ( $i = 1; $i < $n; $i++) { // Consider all elements  // as previous of arr[i] for ($j = 0; $j < $i; $j++) { // If arr[i] is greater then  // check with las[j][1] if ($arr[$j] < $arr[$i] and $las[$i][0] < $las[$j][1] + 1) $las[$i][0] = $las[$j][1] + 1; // If arr[i] is smaller then // check with las[j][0] if($arr[$j] > $arr[$i] and $las[$i][1] < $las[$j][0] + 1) $las[$i][1] = $las[$j][0] + 1; } /* Pick maximum of both  values at index i */ if ($res < max($las[$i][0] $las[$i][1])) $res = max($las[$i][0] $las[$i][1]); } return $res; } // Driver Code $arr = array(10 22 9 33 49 50 31 60 ); $n = count($arr); echo 'Length of Longest alternating ' . 'subsequence is ' zzis($arr $n) ; // This code is contributed by anuj_67. ?>
JavaScript 
<script>  // Javascript program to find longest  // alternating subsequence in an array    // Function to return longest  // alternating subsequence length  function zzis(arr n)  {  /*las[i][0] = Length of the longest  alternating subsequence ending at  index i and last element is  greater than its previous element  las[i][1] = Length of the longest  alternating subsequence ending at  index i and last element is  smaller than its previous  element */  let las = new Array(n);  for (let i = 0; i < n; i++)  {  las[i] = new Array(2);  for (let j = 0; j < 2; j++)  {  las[i][j] = 0;  }  }  /* Initialize all values from 1 */  for (let i = 0; i < n; i++)  las[i][0] = las[i][1] = 1;  let res = 1; // Initialize result  /* Compute values in bottom up manner */  for (let i = 1; i < n; i++)  {  // Consider all elements as  // previous of arr[i]  for (let j = 0; j < i; j++)  {  // If arr[i] is greater then  // check with las[j][1]  if (arr[j] < arr[i] &&  las[i][0] < las[j][1] + 1)  las[i][0] = las[j][1] + 1;  // If arr[i] is smaller then  // check with las[j][0]  if( arr[j] > arr[i] &&  las[i][1] < las[j][0] + 1)  las[i][1] = las[j][0] + 1;  }  /* Pick maximum of both values at  index i */  if (res < Math.max(las[i][0] las[i][1]))  res = Math.max(las[i][0] las[i][1]);  }  return res;  }    let arr = [ 10 22 9 33 49 50 31 60 ];  let n = arr.length;  document.write('Length of Longest '+  'alternating subsequence is ' +  zzis(arr n));    // This code is contributed by rameshtravel07. </script>

Uitvoer 
Length of Longest alternating subsequence is 6

Tijdcomplexiteit: OP2) 
Hulpruimte: O(N) omdat N extra ruimte is ingenomen

Efficiënte aanpak: Om het probleem op te lossen, volgt u het onderstaande idee: 

In de bovenstaande benadering houden we op elk moment twee waarden bij (de lengte van de langste afwisselende deelreeks eindigend op index i en het laatste element is kleiner of groter dan het vorige element) voor elk element in de array. Om de ruimte te optimaliseren hoeven we slechts twee variabelen voor het element op elke index i op te slaan

inc = Lengte van de langste alternatieve deelreeks tot nu toe, waarbij de huidige waarde groter is dan de vorige waarde.
dec = Lengte van de langste alternatieve deelreeks tot nu toe, waarbij de huidige waarde kleiner is dan de vorige waarde.
Het lastige deel van deze aanpak is het bijwerken van deze twee waarden. 

'inc' moet worden verhoogd als en alleen als het laatste element in de alternatieve reeks kleiner was dan het vorige element.
'dec' moet worden verhoogd als en alleen als het laatste element in de alternatieve reeks groter was dan het vorige element.

Volg de onderstaande stappen om het probleem op te lossen:

  • Verklaar dat twee gehele getallen inc en dec gelijk zijn aan één
  • Voer een lus uit voor i [1 N-1]
    • Als arr[i] groter is dan het vorige element, stel dan inc gelijk aan dec + 1
    • Anders, als arr[i] kleiner is dan het vorige element, stel dan dec gelijk aan inc + 1
  • Retour maximaal in- en dec

Hieronder vindt u de implementatie van de bovenstaande aanpak:

C++ 
// C++ program for above approach #include    using namespace std; // Function for finding // longest alternating // subsequence int LAS(int arr[] int n) {  // 'inc' and 'dec' initialized as 1  // as single element is still LAS  int inc = 1;  int dec = 1;  // Iterate from second element  for (int i = 1; i < n; i++) {  if (arr[i] > arr[i - 1]) {  // 'inc' changes if 'dec'  // changes  inc = dec + 1;  }  else if (arr[i] < arr[i - 1]) {  // 'dec' changes if 'inc'  // changes  dec = inc + 1;  }  }  // Return the maximum length  return max(inc dec); } // Driver Code int main() {  int arr[] = { 10 22 9 33 49 50 31 60 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function Call  cout << LAS(arr n) << endl;  return 0; }
Java 
// Java Program for above approach public class GFG {  // Function for finding  // longest alternating  // subsequence  static int LAS(int[] arr int n)  {  // 'inc' and 'dec' initialized as 1  // as single element is still LAS  int inc = 1;  int dec = 1;  // Iterate from second element  for (int i = 1; i < n; i++) {  if (arr[i] > arr[i - 1]) {  // 'inc' changes if 'dec'  // changes  inc = dec + 1;  }  else if (arr[i] < arr[i - 1]) {  // 'dec' changes if 'inc'  // changes  dec = inc + 1;  }  }  // Return the maximum length  return Math.max(inc dec);  }  // Driver Code  public static void main(String[] args)  {  int[] arr = { 10 22 9 33 49 50 31 60 };  int n = arr.length;  // Function Call  System.out.println(LAS(arr n));  } }
Python3 
# Python3 program for above approach def LAS(arr n): # 'inc' and 'dec' initialized as 1 # as single element is still LAS inc = 1 dec = 1 # Iterate from second element for i in range(1 n): if (arr[i] > arr[i-1]): # 'inc' changes if 'dec' # changes inc = dec + 1 elif (arr[i] < arr[i-1]): # 'dec' changes if 'inc' # changes dec = inc + 1 # Return the maximum length return max(inc dec) # Driver Code if __name__ == '__main__': arr = [10 22 9 33 49 50 31 60] n = len(arr) # Function Call print(LAS(arr n))
C# 
// C# program for above approach using System; class GFG {  // Function for finding  // longest alternating  // subsequence  static int LAS(int[] arr int n)  {  // 'inc' and 'dec' initialized as 1  // as single element is still LAS  int inc = 1;  int dec = 1;  // Iterate from second element  for (int i = 1; i < n; i++) {  if (arr[i] > arr[i - 1]) {  // 'inc' changes if 'dec'  // changes  inc = dec + 1;  }  else if (arr[i] < arr[i - 1]) {  // 'dec' changes if 'inc'  // changes  dec = inc + 1;  }  }  // Return the maximum length  return Math.Max(inc dec);  }  // Driver code  static void Main()  {  int[] arr = { 10 22 9 33 49 50 31 60 };  int n = arr.Length;  // Function Call  Console.WriteLine(LAS(arr n));  } } // This code is contributed by divyeshrabadiya07
JavaScript 
<script>  // Javascript program for above approach    // Function for finding  // longest alternating  // subsequence  function LAS(arr n)  {  // 'inc' and 'dec' initialized as 1  // as single element is still LAS  let inc = 1;  let dec = 1;  // Iterate from second element  for (let i = 1; i < n; i++)  {  if (arr[i] > arr[i - 1])  {  // 'inc' changes if 'dec'  // changes  inc = dec + 1;  }  else if (arr[i] < arr[i - 1])  {  // 'dec' changes if 'inc'  // changes  dec = inc + 1;  }  }  // Return the maximum length  return Math.max(inc dec);  }  let arr = [ 10 22 9 33 49 50 31 60 ];  let n = arr.length;    // Function Call  document.write(LAS(arr n));    // This code is contributed by mukesh07. </script>

Uitgang:

.volgende Java 
6

Tijdcomplexiteit: OP) 
Hulpruimte: O(1)

Quiz maken