Una secuencia {x1, x2, .. xn} es una secuencia alterna si sus elementos satisfacen una de las siguientes relaciones:
x1 < x2 > x3 < x4 > x5 < …. xn or x1 > x2 < x3 > x4 < x5 > …. xn
Ejemplos:
Input: arr[] = {1, 5, 4}
Output: 3
The whole arrays is of the form x1 < x2 > x3
Input: arr[] = {1, 4, 5}
Output: 2
All subsequences of length 2 are either of the form
x1 < x2; or x1 > x2
Input: arr[] = {10, 22, 9, 33, 49, 50, 31, 60}
Output: 6
The subsequences {10, 22, 9, 33, 31, 60} or
{10, 22, 9, 49, 31, 60} or {10, 22, 9, 50, 31, 60}
are longest subsequence of length 6.
Este problema es una extensión del problema de la subsecuencia creciente más larga , pero requiere más pensamiento para encontrar la propiedad de subestructura óptima en este.
Resolveremos este problema mediante el método de programación dinámica. Sea A una array de longitud n de números enteros. Definimos una array 2D las[n][2] tal que las[i][0] contiene la subsecuencia alterna más larga que termina en el índice i y el último elemento es mayor que su elemento anterior y las[i][1] contiene la subsecuencia alterna más larga que termina en el índice i y el último elemento es más pequeño que su elemento anterior, entonces tenemos la siguiente relación de recurrencia entre ellos,
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
Recursive Formulation:
las[i][0] = max (las[i][0], las[j][1] + 1);
for all j < i and A[j] < A[i]
las[i][1] = max (las[i][1], las[j][0] + 1);
for all j < i and A[j] > A[i]
La primera relación de recurrencia se basa en el hecho de que, si estamos en la posición i y este elemento tiene que ser más grande que su elemento anterior, entonces para que esta secuencia (hasta i) sea más grande, intentaremos elegir un elemento j (< i) tal que A[j] < A[i], es decir, A[j] puede convertirse en el elemento anterior de A[i] y las[j][1] + 1 es mayor que las[i][0], entonces actualizaremos las[i][0].
Recuerde que hemos elegido las[j][1] + 1 no las[j][0] + 1 para satisfacer la propiedad alternativa porque en las[j][0] el último elemento es más grande que el anterior y A[i] es mayor que A[j], lo que romperá la propiedad alterna si actualizamos. Entonces, el hecho anterior deriva la primera relación de recurrencia, también se puede hacer un argumento similar para la segunda relación de recurrencia.
C++
// C++ program to find longest alternating
// subsequence in an array
#include<iostream>
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 <stdio.h>
#include <stdlib.h>
// 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 program */
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 %d\n",
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 program */
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
// 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>
Producción:
Length of Longest alternating subsequence is 6
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n)
Solución eficiente:
en el enfoque anterior, en cualquier momento hacemos un seguimiento de dos valores (longitud de la subsecuencia alterna más larga que termina en el índice i, y el último elemento es menor o mayor que el elemento anterior), para cada elemento de la array. Para optimizar el espacio, solo necesitamos almacenar dos variables para el elemento en cualquier índice i.
inc = Longitud de la subsecuencia alternativa más larga hasta el momento, siendo el valor actual mayor que su valor anterior.
dec = Longitud de la subsecuencia alternativa más larga hasta el momento con un valor actual menor que su valor anterior.
La parte complicada de este enfoque es actualizar estos dos valores.
“inc” debe aumentarse, si y solo si el último elemento en la secuencia alternativa era más pequeño que su elemento anterior.
“dec” debe aumentarse, si y solo si el último elemento en la secuencia alternativa fue mayor que su elemento anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
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 iff "dec"
// changes
inc = dec + 1;
}
else if (arr[i] < arr[i - 1])
{
// "dec" changes iff "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 iff "dec"
// changes
inc = dec + 1;
}
else if (arr[i] < arr[i - 1])
{
// "dec" changes iff "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 iff "dec" # changes inc = dec + 1 else if (arr[i] < arr[i-1]): # "dec" changes iff "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 iff "dec"
// changes
inc = dec + 1;
}
else if (arr[i] < arr[i - 1])
{
// "dec" changes iff "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 iff "dec"
// changes
inc = dec + 1;
}
else if (arr[i] < arr[i - 1])
{
// "dec" changes iff "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>
Producción:
6
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Utkarsh Trivedi. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA