Dado un arreglo arr[] que contiene n números, la tarea es encontrar la longitud del subarreglo ZigZag más largo tal que cada elemento en el subarreglo debe estar en forma
a < b > c < d > e < f
Ejemplos:
Entrada: arr[] = {12, 13, 1, 5, 4, 7, 8, 10, 10, 11} Salida:
6 Explicación
:
El subarreglo es {12, 13, 1, 5, 4, 7} cuya longitud tiene 6 y está en forma de zigzag.Entrada: array[] = {1, 2, 3, 4, 5}
Salida: 2
Explicación:
El subarreglo es {1, 2} o {2, 3} o {4, 5} cuya longitud es 2.
Enfoque : Para resolver el problema mencionado anteriormente, se siguen los siguientes pasos:
- Inicialmente inicialice cnt , un contador como 1.
- Iterar entre los elementos de la array, verificar si los elementos están en forma
a < b > c < d > e < f
- Si es verdadero Aumenta el cnt en 1. Si no está en forma
a < b > c < d > e < f
- luego reinicializar cnt por 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find
// the length of longest zigzag
// subarray of the given array
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of
// longest zigZag contiguous subarray
int lenOfLongZigZagArr(int a[], int n)
{
// 'max' to store the length
// of longest zigZag subarray
int max = 1,
// 'len' to store the lengths
// of longest zigZag subarray
// at different instants of time
len = 1;
// Traverse the array from the beginning
for (int i = 0; i < n - 1; i++) {
if (i % 2 == 0
&& (a[i] < a[i + 1]))
len++;
else if (i % 2 == 1
&& (a[i] > a[i + 1]))
len++;
else {
// Check if 'max' length
// is less than the length
// of the current zigzag subarray.
// If true, then update 'max'
if (max < len)
max = len;
// Reset 'len' to 1
// as from this element,
// again the length of the
// new zigzag subarray
// is being calculated
len = 1;
}
}
// comparing the length of the last
// zigzag subarray with 'max'
if (max < len)
max = len;
// Return required maximum length
return max;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << lenOfLongZigZagArr(arr, n);
return 0;
}
Java
// Java implementation to find
// the length of longest zigzag
// subarray of the given array
import java.io.*;
import java.util.*;
class GFG {
// Function to find the length of
// longest zigZag contiguous subarray
static int lenOfLongZigZagArr(int a[], int n)
{
// 'max' to store the length
// of longest zigZag subarray
int max = 1,
// 'len' to store the lengths
// of longest zigZag subarray
// at different instants of time
len = 1;
// Traverse the array from the beginning
for (int i = 0; i < n - 1; i++)
{
if (i % 2 == 0 && (a[i] < a[i + 1]))
len++;
else if (i % 2 == 1 && (a[i] > a[i + 1]))
len++;
else
{
// Check if 'max' length
// is less than the length
// of the current zigzag subarray.
// If true, then update 'max'
if (max < len)
max = len;
// Reset 'len' to 1
// as from this element,
// again the length of the
// new zigzag subarray
// is being calculated
len = 1;
}
}
// comparing the length of the last
// zigzag subarray with 'max'
if (max < len)
max = len;
// Return required maximum length
return max;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
System.out.println(lenOfLongZigZagArr(arr, n));
}
}
// This code is contributed by coder001
Python3
# Python3 implementation to find the # length of longest zigzag subarray # of the given array # Function to find the length of # longest zigZag contiguous subarray def lenOfLongZigZagArr(a, n): # '_max' to store the length # of longest zigZag subarray _max = 1 # '_len' to store the lengths # of longest zigZag subarray # at different instants of time _len = 1 # Traverse the array from the beginning for i in range(n - 1): if i % 2 == 0 and a[i] < a[i + 1]: _len += 1 elif i % 2 == 1 and a[i] > a[i + 1]: _len += 1 else: # Check if '_max' length is less than # the length of the current zigzag # subarray. If true, then update '_max' if _max < _len: _max = _len # Reset '_len' to 1 as from this element, # again the length of the new zigzag # subarray is being calculated _len = 1 # Comparing the length of the last # zigzag subarray with '_max' if _max < _len: _max = _len # Return required maximum length return _max # Driver code arr = [ 1, 2, 3, 4, 5 ] n = len(arr) print(lenOfLongZigZagArr(arr, n)) # This code is contributed by divyamohan123
C#
// C# implementation to find
// the length of longest zigzag
// subarray of the given array
using System;
class GFG{
// Function to find the length of
// longest zigZag contiguous subarray
static int lenOflongZigZagArr(int []a, int n)
{
// 'max' to store the length
// of longest zigZag subarray
int max = 1,
// 'len' to store the lengths
// of longest zigZag subarray
// at different instants of time
len = 1;
// Traverse the array from the beginning
for(int i = 0; i < n - 1; i++)
{
if (i % 2 == 0 && (a[i] < a[i + 1]))
len++;
else if (i % 2 == 1 && (a[i] > a[i + 1]))
len++;
else
{
// Check if 'max' length
// is less than the length
// of the current zigzag subarray.
// If true, then update 'max'
if (max < len)
max = len;
// Reset 'len' to 1
// as from this element,
// again the length of the
// new zigzag subarray
// is being calculated
len = 1;
}
}
// Comparing the length of the last
// zigzag subarray with 'max'
if (max < len)
max = len;
// Return required maximum length
return max;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4, 5 };
int n = arr.Length;
Console.WriteLine(lenOflongZigZagArr(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to find
// the length of longest zigzag
// subarray of the given array
// Function to find the length of
// longest zigZag contiguous subarray
function lenOfLongZigZagArr( a, n)
{
// 'max' to store the length
// of longest zigZag subarray
var max = 1,
// 'len' to store the lengths
// of longest zigZag subarray
// at different instants of time
len = 1;
// Traverse the array from the beginning
for (var i = 0; i < n - 1; i++) {
if (i % 2 == 0
&& (a[i] < a[i + 1]))
len++;
else if (i % 2 == 1
&& (a[i] > a[i + 1]))
len++;
else {
// Check if 'max' length
// is less than the length
// of the current zigzag subarray.
// If true, then update 'max'
if (max < len)
max = len;
// Reset 'len' to 1
// as from this element,
// again the length of the
// new zigzag subarray
// is being calculated
len = 1;
}
}
// comparing the length of the last
// zigzag subarray with 'max'
if (max < len)
max = len;
// Return required maximum length
return max;
}
// Driver code
var arr = [ 1, 2, 3, 4, 5 ];
var n = arr.length;
document.write( lenOfLongZigZagArr(arr, n));
</script>
Producción:
2
Análisis de complejidad:
Complejidad de tiempo: O (n), donde n es la longitud de la array.
Espacio auxiliar: O(1), no se requiere espacio adicional.