Longitud del subarreglo alterno más largo

Dada una array de N que incluye solo números positivos y negativos. La tarea es encontrar la longitud del subarreglo alternativo más largo (significa negativo-positivo-negativo o positivo-negativo-positivo) presente en el arreglo. 
Ejemplos: 
 

Input: a[] = {-5, -1, -1, 2, -2, -3}
Output: 3 
The subarray {-1, 2, -2} 

Input: a[] = {1, -5, 1, -5}
Output: 4 

Planteamiento: Para la solución del problema se siguen los siguientes pasos: 
 

  • Inicialmente inicialice cnt como 1.
  • Iterar entre los elementos de la array y verificar si tiene un signo alternativo.
  • Aumente el cnt en 1 si tiene un signo alternativo.
  • Si no tiene un signo alternativo, reinicie cnt en 1.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find the longest alternating
// subarray in an array of N number
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the longest subarray
int longestAlternatingSubarray(int a[], int n)
{
    // Length of longest alternating
    int longest = 1;
    int cnt = 1;
 
    // Iterate in the array
    for (int i = 1; i < n; i++) {
 
        // Check for alternate
        if (a[i] * a[i - 1] < 0) {
            cnt++;
            longest = max(longest, cnt);
        }
        else
            cnt = 1;
    }
    return longest;
}
 
/* Driver program to test above functions*/
int main()
{
    int a[] = { -5, -1, -1, 2, -2, -3 };
    int n = sizeof(a) / sizeof(a[0]);
 
    // Function to find the longest subarray
    cout << longestAlternatingSubarray(a, n);
    return 0;
}

Java

// Java program to find the longest alternating
// subarray in an array of N number
class GFG
{
 
    // Function to find the longest subarray
    static int longestAlternatingSubarray(int a[], int n)
    {
        // Length of longest alternating
        int longest = 1;
        int cnt = 1;
     
        // Iterate in the array
        for (int i = 1; i < n; i++)
        {
     
            // Check for alternate
            if (a[i] * a[i - 1] < 0)
            {
                cnt++;
                longest = Math.max(longest, cnt);
            }
            else
                cnt = 1;
        }
        return longest;
    }
     
    /* Driver program to test above functions*/
    public static void main (String[] args)
    {
        int a[] = { -5, -1, -1, 2, -2, -3 };
        int n = a.length ;
     
        // Function to find the longest subarray
        System.out.println(longestAlternatingSubarray(a, n));
    }
}
 
// This code is contributed by Ryuga

Python 3

# Python3 program to find the longest alternating
# subarray in an array of N number
 
# Function to find the longest subarray
def longestAlternatingSubarray(a, n):
     
    # Length of longest alternating
    longest = 1
    cnt = 1
 
    # Iterate in the array
    i = 1
    while i < n:
 
        # Check for alternate
        if (a[i] * a[i - 1] < 0):
            cnt = cnt + 1
            longest = max(longest, cnt)
         
        else:
            cnt = 1
        i = i + 1
     
    return longest
 
# Driver Code
a = [ -5, -1, -1, 2, -2, -3 ]
n = len(a)
 
# Function to find the longest subarray
print(longestAlternatingSubarray(a, n))
 
# This code is contributed
# by shashank_sharma

C#

// C# program to find the longest alternating
// subarray in an array of N number
using System;
class GFG
{
 
// Function to find the longest subarray
static int longestAlternatingSubarray(int []a,
                                      int n)
{
    // Length of longest alternating
    int longest = 1;
    int cnt = 1;
 
    // Iterate in the array
    for (int i = 1; i < n; i++)
    {
 
        // Check for alternate
        if (a[i] * a[i - 1] < 0)
        {
            cnt++;
            longest = Math.Max(longest, cnt);
        }
        else
            cnt = 1;
    }
    return longest;
}
 
// Driver Code
public static void Main()
{
    int []a = { -5, -1, -1, 2, -2, -3 };
    int n = a.Length;
 
    // Function to find the longest subarray
    Console.Write(longestAlternatingSubarray(a, n));
}
}
 
// This code is contributed
// by Akanksha Rai

PHP

<?php
// PHP program to find the longest alternating
// subarray in an array of N number
 
// Function to find the longest subarray
function longestAlternatingSubarray($a, $n)
{
     
    // Length of longest alternating
    $longest = 1;
    $cnt = 1;
 
    // Iterate in the array
    for ($i = 1; $i < $n; $i++)
    {
 
        // Check for alternate
        if ($a[$i] * $a[$i - 1] < 0)
        {
            $cnt++;
            $longest = max($longest, $cnt);
        }
        else
            $cnt = 1;
    }
    return $longest;
}
 
// Driver Code
$a = array(-5, -1, -1, 2, -2, -3 );
$n = sizeof($a);
 
// Function to find the longest subarray
echo longestAlternatingSubarray($a, $n);
 
// This code is contributed by akt_mit
?>

Javascript

<script>
// JavaScript program to find the longest alternating
// subarray in an array of N number
 
// Function to find the longest subarray
function longestAlternatingSubarray(a, n)
{
 
    // Length of longest alternating
    let longest = 1;
    let cnt = 1;
 
    // Iterate in the array
    for (let i = 1; i < n; i++) {
 
        // Check for alternate
        if (a[i] * a[i - 1] < 0) {
            cnt++;
            longest = Math.max(longest, cnt);
        }
        else
            cnt = 1;
    }
    return longest;
}
 
/* Driver program to test above functions*/
    let a = [ -5, -1, -1, 2, -2, -3 ];
    let n = a.length;
 
    // Function to find the longest subarray
    document.write(longestAlternatingSubarray(a, n));
 
// This code is contributed by Surbhi Tyagi.
</script>
Producción: 

3

 

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es el número de elementos de la array.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.

Publicación traducida automáticamente

Artículo escrito por Striver 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 *