Subsecuencia en zig-zag más larga

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, 
signum(n) = \begin{cases} 1 &\quad\text{if }n > 0\\ -1 &\quad\text{if }n < 0\\ 0 &\quad\text{if }n = 0\\ \end{cases}
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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *