logo

TechCodeview

Længste alternerende efterfølge

En sekvens {X1 X2 .. Xn} er en alternerende sekvens, hvis dens elementer opfylder en af ​​følgende relationer: 

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

Eksempler:



Input: arr[] = {1 5 4}
Produktion: 3
Forklaring: Hele arrays har formen  x1< x2 >x3 

Input: arr[] = {10 22 9 33 49 50 31 60}
Produktion: 6
Forklaring: Efterfølgerne {10 22 9 33 31 60} eller
{10 22 9 49 31 60} eller {10 22 9 50 31 60}
er længste efterfølger af længde 6

Anbefalet praksis Længste alternerende efterfølge Prøv det!

Note: Dette problem er en forlængelse af længst stigende følgeproblem men kræver mere omtanke for at finde optimal underbygningsegenskab i dette

Længste alternerende efterfølge ved hjælp af dynamisk programmering :

Følg nedenstående idé for at løse problemet:

Vi vil løse dette problem ved hjælp af dynamisk programmeringsmetode, da den har optimal understruktur og overlappende underproblemer

markdown billeder

Følg nedenstående trin for at løse problemet:

  • Lad A er givet en matrix med længden N 
  • Vi definerer et 2D-array las[n][2] således, at las[i][0] indeholder den længste alternerende undersekvens, der slutter ved indeks i, og det sidste element er større end dets forrige element 
  • las[i][1] indeholder den længste alternerende undersekvens, der slutter ved indeks i, og det sidste element er mindre end dets forrige element, så har vi følgende gentagelsesrelation mellem dem  

las[i][0] = Længden af ​​den længste alternerende delsekvens 
                  slutter ved indeks i og sidste element er større
                  end dets tidligere element

den[i][1] = Længden af ​​den længste alternerende delsekvens 
                  slutter ved indeks i og sidste element er mindre
                  end dets tidligere element

Rekursiv formulering:

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

   las[i][1] = max (las[i][1] las[j][0] + 1); 
                 for alle j< i and A[j] >A[i]

generel beskyttelsesfejl
  • Den første gentagelsesrelation er baseret på det faktum, at hvis vi er i position i, og dette element skal være større end dets tidligere element, vil vi, for at denne sekvens (op til i) skal være større, forsøge at vælge et element j (< 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]. 
  • Husk, at vi har valgt las[j][1] + 1 ikke las[j][0] + 1 for at tilfredsstille den alternative egenskab, fordi i las[j][0] er det sidste element større end dets forrige, og A[i] er større end A[j], hvilket vil bryde den alternerende egenskab, hvis vi opdaterer. Så ovenstående kendsgerning udleder den første gentagelsesrelation, et lignende argument kan også fremføres for den anden gentagelsesrelation. 

Nedenfor er implementeringen af ​​ovenstående tilgang:

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>

Produktion 
Length of Longest alternating subsequence is 6

Tidskompleksitet: PÅ2) 
Hjælpeplads: O(N) da der er taget N ekstra plads

Effektiv tilgang: Følg nedenstående idé for at løse problemet: 

I ovenstående tilgang holder vi til enhver tid styr på to værdier (længden af ​​den længste alternerende undersekvens, der slutter ved indeks i, og det sidste element er mindre end eller større end det foregående element) for hvert element i arrayet. For at optimere plads behøver vi kun at gemme to variable for element ved ethvert indeks i

inc = Længden af ​​den hidtil længste alternative undersekvens, hvor den aktuelle værdi er større end dens tidligere værdi.
dec = Længden af ​​den hidtil længste alternative undersekvens, hvor den nuværende værdi er mindre end dens tidligere værdi.
Den vanskelige del af denne tilgang er at opdatere disse to værdier. 

'inc' bør øges, hvis og kun hvis det sidste element i den alternative sekvens var mindre end det forrige element.
'dec' bør øges, hvis og kun hvis det sidste element i den alternative sekvens var større end det forrige element.

Følg nedenstående trin for at løse problemet:

  • Erklær to heltal inc og dec lig med et
  • Kør en løkke for i [1 N-1]
    • Hvis arr[i] er større end det foregående element, så sæt inc lig med dec + 1
    • Ellers hvis arr[i] er mindre end det foregående element, så sæt dec lig med inc + 1
  • Returner maks. ind- og nedtagning

Nedenfor er implementeringen af ​​ovenstående tilgang:

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>

Produktion:

Skuespillerinde Sai Pallavi 
6

Tidskompleksitet: PÅ) 
Hjælpeplads: O(1)

Opret quiz