logo

TechCodeview

Най-дългата редуваща се подпоследователност

Поредица {X1 X2 .. Xn} е редуваща се поредица, ако нейните елементи удовлетворяват едно от следните отношения: 

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

Примери:



вход: arr[] = {1 5 4}
Изход: 3
Обяснение: Целият масив е във формата  x1< x2 >x3 

вход: arr[] = {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

Препоръчителна практика Най-дългата редуваща се подпоследователност Опитайте!

Забележка: Този проблем е продължение на проблем с най-дългата нарастваща подпоследователност но изисква повече мислене за намиране на оптимално свойство на субструктура в това

Използване на най-дългата редуваща се подпоследователност динамично програмиране :

За да разрешите проблема, следвайте идеята по-долу:

Ще разрешим този проблем чрез метода на динамично програмиране, тъй като той има оптимална подструктура и припокриващи се подпроблеми

svm

Следвайте стъпките по-долу, за да разрешите проблема:

  • Нека на A е даден масив с дължина N 
  • Ние дефинираме 2D масив las[n][2] така, че las[i][0] съдържа най-дългата редуваща се подпоследователност, завършваща на индекс i и последният елемент е по-голям от предишния си елемент 
  • las[i][1] съдържа най-дългата редуваща се подпоследователност, завършваща на индекс i и последният елемент е по-малък от предишния си елемент, тогава имаме следната връзка на повторение между тях  

las[i][0] = Дължина на най-дългата редуваща се подпоследователност 
                  завършващ на индекс i и последният елемент е по-голям
                  отколкото предишния му елемент

промяна на името на директорията linux

the[i][1] = Дължина на най-дългата редуваща се подпоследователност 
                  завършващ на индекс i и последният елемент е по-малък
                  отколкото предишния му елемент

Рекурсивна формулировка:

   las[i][0] = max (las[i][0] las[j][1] + 1); 
                  за всички j< i and A[j] < A[i] 

   las[i][1] = max (las[i][1] las[j][0] + 1); 
                 за всички j< i and A[j] >A[i]

  • Първата рекурентна връзка се основава на факта, че ако сме на позиция i и този елемент трябва да е по-голям от предишния си елемент, тогава за да бъде тази последователност (до i) по-голяма, ще се опитаме да изберем елемент 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]. 
  • Не забравяйте, че избрахме las[j][1] + 1, а не las[j][0] + 1, за да удовлетворим алтернативното свойство, защото в las[j][0] последният елемент е по-голям от предишния и A[i] е по-голямо от A[j], което ще наруши алтернативното свойство, ако актуализираме. Така че горният факт извежда първата рекурентна връзка, подобен аргумент може да се направи и за втората рекурентна връзка. 

По-долу е изпълнението на горния подход:

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

Времева сложност: O(N2) 
Помощно пространство: O(N), тъй като е заето N допълнително място

Ефикасен подход: За да разрешите проблема, следвайте идеята по-долу: 

В горния подход във всеки момент ние следим две стойности (дължината на най-дългата редуваща се подпоследователност, завършваща на индекс i и последният елемент е по-малък или по-голям от предишния елемент) за всеки елемент от масива. За да оптимизираме пространството, трябва само да съхраним две променливи за елемент при всеки индекс i

inc = Дължина на най-дългата алтернативна подпоследователност досега, като текущата стойност е по-голяма от предишната стойност.
dec = Дължина на най-дългата алтернативна подпоследователност досега, като текущата стойност е по-малка от предишната стойност.
Сложната част от този подход е да актуализирате тези две стойности. 

низ concat java

'inc' трябва да се увеличи тогава и само ако последният елемент в алтернативната последователност е по-малък от предишния си елемент.
'dec' трябва да се увеличи, ако и само ако последният елемент в алтернативната последователност е по-голям от предишния си елемент.

Следвайте стъпките по-долу, за да разрешите проблема:

  • Декларирайте две цели числа inc и dec равни на едно
  • Изпълнение на цикъл за i [1 N-1]
    • Ако arr[i] е по-голям от предишния елемент, тогава задайте inc равно на dec + 1
    • В противен случай, ако arr[i] е по-малък от предишния елемент, тогава задайте dec равно на inc + 1
  • Върнете максимум от inc и dec

По-долу е изпълнението на горния подход:

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

Времева сложност: O(N) 
Помощно пространство: О(1)

Създаване на тест