El problema de la subsecuencia Zig-Zag más larga es encontrar la longitud de la subsecuencia más larga de una secuencia dada de modo que todos los elementos de esta se alternen.
Si una secuencia {x1, x2, .. xn} es una secuencia alterna, entonces su elemento satisface 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 Zig-Zag 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 Z[n][2] tal que Z[i][0] contiene la subsecuencia Zig-Zag más larga que termina en el índice i y el último elemento es mayor que su elemento anterior y Z[i][1] contiene la subsecuencia más larga La subsecuencia Zig-Zag 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,
Z[i][0] = Length of the longest Zig-Zag subsequence
ending at index i and last element is greater
than its previous element
Z[i][1] = Length of the longest Zig-Zag subsequence
ending at index i and last element is smaller
than its previous element
Recursive Formulation:
Z[i][0] = max (Z[i][0], Z[j][1] + 1);
for all j < i and A[j] < A[i]
Z[i][1] = max (Z[i][1], Z[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 Z[j][1] + 1 es mayor que Z[i][0], entonces actualizaremos Z[i][0].
Recuerde que hemos elegido Z[j][1] + 1 no Z[j][0] + 1 para satisfacer la propiedad alternativa porque en Z[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 Zig-Zag subsequence in
// an array
#include <bits/stdc++.h>
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 Zig-Zag subsequence length
int zzis(int arr[], int n)
{
/*Z[i][0] = Length of the longest Zig-Zag subsequence
ending at index i and last element is greater
than its previous element
Z[i][1] = Length of the longest Zig-Zag subsequence
ending at index i and last element is smaller
than its previous element */
int Z[n][2];
/* Initialize all values from 1 */
for (int i = 0; i < n; i++)
Z[i][0] = Z[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 Z[j][1]
if (arr[j] < arr[i] && Z[i][0] < Z[j][1] + 1)
Z[i][0] = Z[j][1] + 1;
// If arr[i] is smaller, then check with Z[j][0]
if( arr[j] > arr[i] && Z[i][1] < Z[j][0] + 1)
Z[i][1] = Z[j][0] + 1;
}
/* Pick maximum of both values at index i */
if (res < max(Z[i][0], Z[i][1]))
res = max(Z[i][0], Z[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]);
cout<<"Length of Longest Zig-Zag subsequence is "<<zzis(arr, n)<<endl;
return 0;
}
// This code is contributed by noob2000.
C
// C program to find longest Zig-Zag 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 Zig-Zag subsequence length
int zzis(int arr[], int n)
{
/*Z[i][0] = Length of the longest Zig-Zag subsequence
ending at index i and last element is greater
than its previous element
Z[i][1] = Length of the longest Zig-Zag subsequence
ending at index i and last element is smaller
than its previous element */
int Z[n][2];
/* Initialize all values from 1 */
for (int i = 0; i < n; i++)
Z[i][0] = Z[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 Z[j][1]
if (arr[j] < arr[i] && Z[i][0] < Z[j][1] + 1)
Z[i][0] = Z[j][1] + 1;
// If arr[i] is smaller, then check with Z[j][0]
if( arr[j] > arr[i] && Z[i][1] < Z[j][0] + 1)
Z[i][1] = Z[j][0] + 1;
}
/* Pick maximum of both values at index i */
if (res < max(Z[i][0], Z[i][1]))
res = max(Z[i][0], Z[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 Zig-Zag subsequence is %d\n",
zzis(arr, n) );
return 0;
}
Java
// Java program to find longest
// Zig-Zag subsequence in an array
import java.io.*;
class GFG {
// Function to return longest
// Zig-Zag subsequence length
static int zzis(int arr[], int n)
{
/*Z[i][0] = Length of the longest
Zig-Zag subsequence ending at
index i and last element is
greater than its previous element
Z[i][1] = Length of the longest
Zig-Zag subsequence ending at
index i and last element is
smaller than its previous
element */
int Z[][] = new int[n][2];
/* Initialize all values from 1 */
for (int i = 0; i < n; i++)
Z[i][0] = Z[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 Z[j][1]
if (arr[j] < arr[i] &&
Z[i][0] < Z[j][1] + 1)
Z[i][0] = Z[j][1] + 1;
// If arr[i] is smaller, then
// check with Z[j][0]
if( arr[j] > arr[i] &&
Z[i][1] < Z[j][0] + 1)
Z[i][1] = Z[j][0] + 1;
}
/* Pick maximum of both values at
index i */
if (res < Math.max(Z[i][0], Z[i][1]))
res = Math.max(Z[i][0], Z[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 "+
"Zig-Zag subsequence is " +
zzis(arr, n));
}
}
// This code is contributed by Prerna Saini
Python3
# Python3 program to find longest
# Zig-Zag subsequence in an array
# Function to return max of two numbers
# Function to return longest
# Zig-Zag subsequence length
def zzis(arr, n):
'''Z[i][0] = Length of the longest Zig-Zag subsequence
ending at index i and last element is greater
than its previous element
Z[i][1] = Length of the longest Zig-Zag subsequence
ending at index i and last element is smaller
than its previous element '''
Z = [[1 for i in range(2)] for i in range(n)]
res = 1 # Initialize result
# Compute values in bottom up manner '''
for i in range(1, n):
# Consider all elements as previous of arr[i]
for j in range(i):
# If arr[i] is greater, then check with Z[j][1]
if (arr[j] < arr[i] and Z[i][0] < Z[j][1] + 1):
Z[i][0] = Z[j][1] + 1
# If arr[i] is smaller, then check with Z[j][0]
if( arr[j] > arr[i] and Z[i][1] < Z[j][0] + 1):
Z[i][1] = Z[j][0] + 1
# Pick maximum of both values at index i '''
if (res < max(Z[i][0], Z[i][1])):
res = max(Z[i][0], Z[i][1])
return res
# Driver Code
arr = [10, 22, 9, 33, 49, 50, 31, 60]
n = len(arr)
print("Length of Longest Zig-Zag subsequence is",
zzis(arr, n))
# This code is contributed by Mohit Kumar
C#
// C# program to find longest
// Zig-Zag subsequence in an array
using System;
class GFG
{
// Function to return longest
// Zig-Zag subsequence length
static int zzis(int []arr, int n)
{
/*Z[i][0] = Length of the longest
Zig-Zag subsequence ending at
index i and last element is
greater than its previous element
Z[i][1] = Length of the longest
Zig-Zag subsequence ending at
index i and last element is
smaller than its previous
element */
int [,]Z = new int[n, 2];
/* Initialize all values from 1 */
for (int i = 0; i < n; i++)
Z[i, 0] = Z[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 Z[j][1]
if (arr[j] < arr[i] &&
Z[i, 0] < Z[j, 1] + 1)
Z[i, 0] = Z[j, 1] + 1;
// If arr[i] is smaller, then
// check with Z[j][0]
if( arr[j] > arr[i] &&
Z[i, 1] < Z[j, 0] + 1)
Z[i, 1] = Z[j, 0] + 1;
}
/* Pick maximum of both values at
index i */
if (res < Math.Max(Z[i, 0], Z[i, 1]))
res = Math.Max(Z[i, 0], Z[i, 1]);
}
return res;
}
// Driver Code
static public void Main ()
{
int []arr = {10, 22, 9, 33,
49, 50, 31, 60};
int n = arr.Length;
Console.WriteLine("Length of Longest "+
"Zig-Zag subsequence is " +
zzis(arr, n));
}
}
// This code is contributed by ajit
PHP
<?php
//PHP program to find longest Zig-Zag
//subsequence in an array
// function to return max of two numbers
function maxD($a, $b) {
return ($a > $b) ? $a : $b;
}
// Function to return longest Zig-Zag subsequence length
function zzis($arr, $n)
{
/*Z[i][0] = Length of the longest Zig-Zag subsequence
ending at index i and last element is greater
than its previous element
Z[i][1] = Length of the longest Zig-Zag subsequence
ending at index i and last element is smaller
than its previous element */
//$Z[$n][2];
/* Initialize all values from 1 */
for ($i = 0; $i < $n; $i++)
$Z[$i][0] = $Z[$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 Z[j][1]
if ($arr[$j] < $arr[$i] && $Z[$i][0] < $Z[$j][1] + 1)
$Z[$i][0] = $Z[$j][1] + 1;
// If arr[i] is smaller, then check with Z[j][0]
if( $arr[$j] > $arr[$i] && $Z[$i][1] < $Z[$j][0] + 1)
$Z[$i][1] = $Z[$j][0] + 1;
}
/* Pick maximum of both values at index i */
if ($res < max($Z[$i][0], $Z[$i][1]))
$res = max($Z[$i][0], $Z[$i][1]);
}
return $res;
}
/* Driver program */
$arr = array( 10, 22, 9, 33, 49, 50, 31, 60 );
$n = sizeof($arr);
echo "Length of Longest Zig-Zag subsequence is ",
zzis($arr, $n) ;
echo "\n";
#This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to find longest
// Zig-Zag subsequence in an array
// Function to return longest
// Zig-Zag subsequence length
function zzis(arr, n)
{
/*Z[i][0] = Length of the longest
Zig-Zag subsequence ending at
index i and last element is
greater than its previous element
Z[i][1] = Length of the longest
Zig-Zag subsequence ending at
index i and last element is
smaller than its previous
element */
let Z = new Array(n);
for(let i = 0; i < n; i++)
{
Z[i] = new Array(2);
}
/* Initialize all values from 1 */
for (let i = 0; i < n; i++)
Z[i][0] = Z[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 Z[j][1]
if (arr[j] < arr[i] &&
Z[i][0] < Z[j][1] + 1)
Z[i][0] = Z[j][1] + 1;
// If arr[i] is smaller, then
// check with Z[j][0]
if( arr[j] > arr[i] &&
Z[i][1] < Z[j][0] + 1)
Z[i][1] = Z[j][0] + 1;
}
/* Pick maximum of both values at
index i */
if (res < Math.max(Z[i][0], Z[i][1]))
res = Math.max(Z[i][0], Z[i][1]);
}
return res;
}
let arr = [ 10, 22, 9, 33, 49, 50, 31, 60 ];
let n = arr.length;
document.write("Length of Longest "+ "Zig-Zag subsequence is " + zzis(arr, n));
</script>
Producción :
Length of Longest Zig-Zag subsequence is 6
Complejidad de tiempo: O(n 2 )
Espacio auxiliar: O(n) A continuación se explica
un mejor enfoque con la complejidad de tiempo O(n)
: Deje que la secuencia se almacene en una array de enteros sin ordenar arr[N].
Procederemos comparando los signos matemáticos (negativo o positivo) de la diferencia de dos elementos consecutivos de arr. Para ello almacenaremos el signo de (arr[i] – arr[i-1]) en una variable, comparándolo posteriormente con el de (arr[i+1] – arr[i]). Si es diferente, incrementaremos nuestro resultado. Para verificar el signo, usaremos una función Signum simple , que determinará el signo de un número que se le pasa. Eso es, 
Considerando el hecho de que recorremos la secuencia solo una vez, esto se convierte en una solución O(n) .
El algoritmo para el enfoque discutido anteriormente es:
Input integer array seq[N].
Initialize integer lastSign to 0.
FOR i in range 1 to N - 1
integer sign = signum(seq[i] - seq[i-1])
IF sign != lastSign AND IF sign != 0
increment length by 1. lastSign = sign.
END IF
END FOR
return length.
La siguiente es la implementación del enfoque anterior:
C++
/*CPP program to find the maximum length of zig-zag
sub-sequence in given sequence*/
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function prototype.
int signum(int n);
/* Function to calculate maximum length of zig-zag
sub-sequence in given sequence.
*/
int maxZigZag(int seq[], int n)
{
if (n == 0) {
return 0;
}
int lastSign = 0, length = 1;
// Length is initialized to 1 as
// that is minimum value
// for arbitrary sequence.
for (int i = 1; i < n; ++i) {
int Sign = signum(seq[i] - seq[i - 1]);
// It qualifies
if (Sign != lastSign && Sign != 0)
{
// Updating lastSign
lastSign = Sign;
length++;
}
}
return length;
}
/* Signum function :
Returns 1 when passed a positive integer
Returns -1 when passed a negative integer
Returns 0 when passed 0. */
int signum(int n)
{
if (n != 0) {
return n > 0 ? 1 : -1;
}
else {
return 0;
}
}
// Driver method
int main()
{
int sequence1[4] = { 1, 3, 6, 2 };
int sequence2[5] = { 5, 0, 3, 1, 0 };
int n1 = sizeof(sequence1)
/ sizeof(*sequence1); // size of sequences
int n2 = sizeof(sequence2) / sizeof(*sequence2);
int maxLength1 = maxZigZag(sequence1, n1);
int maxLength2
= maxZigZag(sequence2, n2); // function call
cout << "The maximum length of zig-zag sub-sequence in "
"first sequence is: "
<< maxLength1;
cout << endl;
cout << "The maximum length of zig-zag sub-sequence in "
"second sequence is: "
<< maxLength2;
}
Java
// Java code to find out maximum length of zig-zag
// sub-sequence in given sequence
class zigZagMaxLength {
// Driver method
public static void main(String[] args)
{
int[] sequence1 = { 1, 3, 6, 2 };
int[] sequence2 = { 5, 0, 3, 1, 0 };
int n1 = sequence1.length; // size of sequences
int n2 = sequence2.length;
int maxLength1 = maxZigZag(sequence1, n1);
int maxLength2
= maxZigZag(sequence2, n2); // function call
System.out.println(
"The maximum length of zig-zag sub-sequence in first sequence is: "
+ maxLength1);
System.out.println(
"The maximum length of zig-zag sub-sequence in second sequence is: "
+ maxLength2);
}
/* Function to calculate maximum length of zig-zag
sub-sequence in given sequence.
*/
static int maxZigZag(int[] seq, int n)
{
if (n == 0) {
return 0;
}
int lastSign = 0, length = 1;
// length is initialized to 1 as that is minimum
// value for arbitrary sequence.
for (int i = 1; i < n; ++i) {
int Sign = signum(seq[i] - seq[i - 1]);
if (Sign != 0
&& Sign != lastSign) // it qualifies
{
lastSign = Sign; // updating lastSign
length++;
}
}
return length;
}
/* Signum function :
Returns 1 when passed a positive integer
Returns -1 when passed a negative integer
Returns 0 when passed 0. */
static int signum(int n)
{
if (n != 0) {
return n > 0 ? 1 : -1;
}
else {
return 0;
}
}
}
Python3
# Python3 program to find the maximum
# length of zig-zag sub-sequence in
# given sequence
# Function to calculate maximum length
# of zig-zag sub-sequence in given sequence.
def maxZigZag(seq, n):
if (n == 0):
return 0
lastSign = 0
# Length is initialized to 1 as that is
# minimum value for arbitrary sequence
length = 1
for i in range(1, n):
Sign = signum(seq[i] - seq[i - 1])
# It qualifies
if (Sign != lastSign and Sign != 0):
# Updating lastSign
lastSign = Sign
length += 1
return length
# Signum function :
# Returns 1 when passed a positive integer
# Returns -1 when passed a negative integer
# Returns 0 when passed 0.
def signum(n):
if (n != 0):
return 1 if n > 0 else -1
else:
return 0
# Driver code
if __name__ == '__main__':
sequence1 = [1, 3, 6, 2]
sequence2 = [5, 0, 3, 1, 0]
n1 = len(sequence1)
n2 = len(sequence2)
# Function call
maxLength1 = maxZigZag(sequence1, n1)
maxLength2 = maxZigZag(sequence2, n2)
print("The maximum length of zig-zag sub-sequence "
"in first sequence is:", maxLength1)
print("The maximum length of zig-zag sub-sequence "
"in second sequence is:", maxLength2)
# This code is contributed by himanshu77
C#
// C# code to find out maximum length of
// zig-zag sub-sequence in given sequence
using System;
class zigZagMaxLength {
// Driver method
public static void Main(String[] args)
{
int[] sequence1 = { 1, 3, 6, 2 };
int[] sequence2 = { 5, 0, 3, 1, 0 };
int n1 = sequence1.Length; // size of sequences
int n2 = sequence2.Length;
int maxLength1 = maxZigZag(sequence1, n1);
int maxLength2
= maxZigZag(sequence2, n2); // function call
Console.WriteLine(
"The maximum length of zig-zag sub-sequence"
+ " in first sequence is: " + maxLength1);
Console.WriteLine(
"The maximum length of zig-zag "
+ "sub-sequence in second sequence is: "
+ maxLength2);
}
/* Function to calculate maximum length of zig-zag
sub-sequence in given sequence.
*/
static int maxZigZag(int[] seq, int n)
{
if (n == 0) {
return 0;
}
// length is initialized to 1 as that is minimum
// value for arbitrary sequence.
int lastSign = 0, length = 1;
for (int i = 1; i < n; ++i) {
int Sign = signum(seq[i] - seq[i - 1]);
if (Sign != 0
&& Sign != lastSign) // it qualifies
{
lastSign = Sign; // updating lastSign
length++;
}
}
return length;
}
/* Signum function :
Returns 1 when passed a positive integer
Returns -1 when passed a negative integer
Returns 0 when passed 0. */
static int signum(int n)
{
if (n != 0) {
return n > 0 ? 1 : -1;
}
else {
return 0;
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript code to find out maximum length of
// zig-zag sub-sequence in given sequence
/* Function to calculate maximum length of zig-zag
sub-sequence in given sequence.
*/
function maxZigZag(seq, n)
{
if (n == 0) {
return 0;
}
// length is initialized to 1 as that is minimum
// value for arbitrary sequence.
let lastSign = 0, length = 1;
for (let i = 1; i < n; ++i) {
let Sign = signum(seq[i] - seq[i - 1]);
if (Sign != 0 && Sign != lastSign) // it qualifies
{
lastSign = Sign; // updating lastSign
length++;
}
}
return length;
}
/* Signum function :
Returns 1 when passed a positive integer
Returns -1 when passed a negative integer
Returns 0 when passed 0. */
function signum(n)
{
if (n != 0) {
return n > 0 ? 1 : -1;
}
else {
return 0;
}
}
let sequence1 = [ 1, 3, 6, 2 ];
let sequence2 = [ 5, 0, 3, 1, 0 ];
let n1 = sequence1.length; // size of sequences
let n2 = sequence2.length;
let maxLength1 = maxZigZag(sequence1, n1);
let maxLength2 = maxZigZag(sequence2, n2); // function call
document.write("The maximum length of zig-zag sub-sequence"
+ " in first sequence is: " + maxLength1 + "</br>");
document.write(
"The maximum length of zig-zag "
+ "sub-sequence in second sequence is: "
+ maxLength2 + "</br>");
</script>
Producción :
The maximum length of zig-zag sub-sequence in first sequence is: 3 The maximum length of zig-zag sub-sequence in second sequence is: 4
Complejidad del tiempo: 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