logo

TechCodeview

Cea mai lungă secvență alternativă

O secvență {X1 X2 .. Xn} este o secvență alternativă dacă elementele sale satisfac una dintre următoarele relații: 

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

Exemple:



Intrare: arr[] = {1 5 4}
Ieșire: 3
Explicaţie: Întreaga matrice are forma  x1< x2 >x3 

Intrare: arr[] = {10 22 9 33 49 50 31 60}
Ieșire: 6
Explicaţie: Subsecvențele {10 22 9 33 31 60} sau
{10 22 9 49 31 60} sau {10 22 9 50 31 60}
sunt cea mai lungă succesiune a lungimii 6

Practică recomandată Cea mai lungă secvență alternativă Încearcă!

Nota: Această problemă este o extensie a problema de succesiune cu cea mai lungă creștere dar necesită mai multă gândire pentru a găsi proprietatea optimă a substructurii în aceasta

Cea mai lungă secvență alternativă folosind programare dinamică :

Pentru a rezolva problema urmați ideea de mai jos:

Vom rezolva această problemă prin metoda de programare dinamică, deoarece are substructură optimă și subprobleme suprapuse

filigran în cuvânt

Urmați pașii de mai jos pentru a rezolva problema:

  • Fie A are un tablou de lungime N 
  • Definim o matrice 2D las[n][2] astfel încât las[i][0] conține cea mai lungă subsecvență alternativă care se termină la indicele i și ultimul element este mai mare decât elementul său anterior 
  • las[i][1] conține cea mai lungă subsecvență alternativă care se termină la indicele i și ultimul element este mai mic decât elementul anterior, atunci avem următoarea relație de recurență între ele  

la[i][0] = Lungimea celei mai lungi subsecvente alternante 
                  se termină la indicele i și ultimul element este mai mare
                  decât elementul său anterior

cel[i][1] = Lungimea celei mai lungi subsecvente alternante 
                  se termină la indicele i și ultimul element este mai mic
                  decât elementul său anterior

Formulare recursiva:

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

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

  • Prima relație de recurență se bazează pe faptul că, dacă ne aflăm în poziția i și acest element trebuie să fie mai mare decât elementul anterior, atunci pentru ca această secvență (până la i) să fie mai mare vom încerca să alegem un 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]. 
  • Amintiți-vă că am ales las[j][1] + 1 nu las[j][0] + 1 pentru a satisface proprietatea alternativă deoarece în las[j][0] ultimul element este mai mare decât cel anterior și A[i] este mai mare decât A[j], ceea ce va rupe proprietatea alternativă dacă actualizăm. Deci de mai sus derivă prima relație de recurență, un argument similar poate fi făcut și pentru a doua relație de recurență. 

Mai jos este implementarea abordării de mai sus:

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>

Ieșire 
Length of Longest alternating subsequence is 6

Complexitatea timpului: PE2) 
Spațiu auxiliar: O(N) deoarece a fost ocupat N spațiu suplimentar

ce face ravel în python

Abordare eficientă: Pentru a rezolva problema urmați ideea de mai jos: 

matrice de șiruri de caractere c programare

În abordarea de mai sus, urmărim în orice moment două valori (lungimea celei mai lungi secvențe alternante care se termină la indicele i și ultimul element este mai mic sau mai mare decât elementul anterior) pentru fiecare element din matrice. Pentru a optimiza spațiul, trebuie doar să stocăm două variabile pentru element la orice indice i

inc = Lungimea celei mai lungi subsecvențe alternative de până acum, valoarea curentă fiind mai mare decât valoarea anterioară.
dec = Lungimea celei mai lungi subsecvențe alternative de până acum, valoarea curentă fiind mai mică decât valoarea anterioară.
Partea dificilă a acestei abordări este actualizarea acestor două valori. 

„inc” ar trebui crescut dacă și numai dacă ultimul element din secvența alternativă a fost mai mic decât elementul anterior.
„dec” ar trebui crescut dacă și numai dacă ultimul element din secvența alternativă a fost mai mare decât elementul anterior.

Urmați pașii de mai jos pentru a rezolva problema:

  • Declarați două numere întregi inc și dec egale cu unu
  • Rulați o buclă pentru i [1 N-1]
    • Dacă arr[i] este mai mare decât elementul anterior, atunci setați inc egal cu dec + 1
    • Altfel, dacă arr[i] este mai mic decât elementul anterior, atunci setați dec egal cu inc + 1
  • Retur maxim de inc și dec

Mai jos este implementarea abordării de mai sus:

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>

Ieșire: 

6

Complexitatea timpului: PE) 
Spațiu auxiliar: O(1)

Creați un test