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.