logo

TechCodeview

Најдужа наизменична подсеквенца

Низ {Кс1 Кс2 .. Ксн} је наизменични низ ако његови елементи задовољавају једну од следећих релација: 

  Кс1< X2 >Кс3< X4 >Кс5< …. xn or 
  Кс1 > Кс2< X3 >Кс4< X5 >…. кн

Примери:



Улаз: арр[] = {1 5 4}
Излаз: 3
Објашњење: Цео низови су облика  к1< x2 >к3 

Улаз: арр[] = {10 22 9 33 49 50 31 60}
Излаз: 6
Објашњење: Поднизови {10 22 9 33 31 60} или
{10 22 9 49 31 60} или {10 22 9 50 31 60}
су најдужи подниз дужине 6

Препоручена пракса Најдужа наизменична подсеквенца Покушајте!

Напомена: Овај проблем је проширење проблем најдуже растуће подсеквенце али захтева више размишљања за проналажење оптималног својства подструктуре у овоме

Коришћење најдуже наизменичне подсеквенце динамичко програмирање :

Да бисте решили проблем, следите следећу идеју:

Овај проблем ћемо решити методом динамичког програмирања јер има оптималну подструктуру и подпроблеме који се преклапају

спојеви и врсте спојева

Пратите доле наведене кораке да бисте решили проблем:

  • Нека је А дат низ дужине Н 
  • Дефинишемо 2Д низ лас[н][2] тако да лас[и][0] садржи најдужу наизменичну подниз који се завршава на индексу и и да је последњи елемент већи од претходног елемента 
  • лас[и][1] садржи најдужу наизменичну подниз који се завршава на индексу и и последњи елемент је мањи од претходног елемента, онда имамо следећу рекурентну релацију између њих  

лас[и][0] = Дужина најдуже наизменичне поднизе 
                  завршава се на индексу и и последњи елемент је већи
                  него њен претходни елемент

[и][1] = Дужина најдуже наизменичне поднизе 
                  завршава се на индексу и и последњи елемент је мањи
                  него њен претходни елемент

Рекурзивна формулација:

   лас[и][0] = мак (лас[и][0] лас[ј][1] + 1); 
                  за све ј< i and A[j] < A[i] 

   лас[и][1] = мак (лас[и][1] лас[ј][0] + 1); 
                 за све ј< i and A[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]. 
  • Запамтите да смо изабрали лас[ј][1] + 1, а не лас[ј][0] + 1 да бисмо задовољили алтернативно својство јер је у лас[ј][0] последњи елемент већи од претходног и А[и] је већи од А[ј] што ће покварити својство наизменичне употребе ако ажурирамо. Дакле, горња чињеница изводи прву рекурентну релацију, сличан аргумент се може дати и за другу рекурентну релацију. 

Испод је примена горњег приступа:

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>

Излаз 
Length of Longest alternating subsequence is 6

Временска сложеност: О(Н2) 
Помоћни простор: О(Н) пошто је заузето Н додатног простора

Ефикасан приступ: Да бисте решили проблем, следите следећу идеју: 

У горњем приступу у сваком тренутку пратимо две вредности (дужина најдуже наизменичне подниз који се завршава на индексу и и последњи елемент је мањи или већи од претходног елемента) за сваки елемент у низу. Да бисмо оптимизовали простор, потребно је само да ускладиштимо две променљиве за елемент у било ком индексу и

инц = Дужина најдуже алтернативне подниз до сада са тренутном вредношћу која је већа од претходне вредности.
дец = Дужина најдуже алтернативне подниз до сада са тренутном вредношћу која је мања од претходне вредности.
Тежак део овог приступа је ажурирање ове две вредности. 

'инц' треба повећати ако и само ако је последњи елемент у алтернативној секвенци мањи од претходног елемента.
'дец' треба повећати ако и само ако је последњи елемент у алтернативном низу већи од претходног елемента.

Пратите доле наведене кораке да бисте решили проблем:

  • Прогласите два цела броја инц и дец једнакима једном
  • Покрените петљу за и [1 Н-1]
    • Ако је арр[и] већи од претходног елемента, онда поставите инц на дец + 1
    • Иначе, ако је арр[и] мањи од претходног елемента, онда подесите дец на инц + 1
  • Поврати максимум инц и дец

Испод је примена горњег приступа:

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>

Излаз:

упореди са Јавом 
6

Временска сложеност: О(Н) 
Помоћни простор: О(1)

Креирај квиз