Dada una array arr[] de N elementos. La tarea es encontrar la longitud del subarreglo más largo tal que el producto del subarreglo sea negativo. Si no hay tal subarreglo disponible, imprima -1.
Ejemplos:
Entrada: N = 6, arr[] = {-1, 2, 3, 2, 1, -4}
Salida: 5
Explicación:
En el ejemplo, el subarreglo
en el rango [1, 5] tiene un producto -12 que es negativo,
entonces la longitud es 5.
Entrada: N = 4, arr[] = {1, 2, 3, 2}
Salida: -1
Acercarse:
- Primero, verifique si el producto total de la array es negativo. Si el producto total de la array es negativo, la respuesta será N.
- Si el producto total de la array no es negativo, significa que es positivo. Entonces, la idea es encontrar un elemento negativo de la array tal que excluyendo ese elemento y comparando la longitud de ambas partes de la array podemos obtener la longitud máxima de la subarreglo con el producto negativo.
- Es obvio que el-
existirá un subarreglo con producto negativo en el rango [1, x) o (x, N], donde 1 <= x <= N, y arr[x] es negativo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find length of the
// longest subarray such that product
// of the subarray is negative
int maxLength(int a[], int n)
{
int product = 1, len = -1;
// Check if product of complete
// array is negative
for (int i = 0; i < n; i++)
product *= a[i];
// Total product is already
// negative
if (product < 0)
return n;
// Find an index i such the a[i]
// is negative and compare length
// of both halfs excluding a[i] to
// find max length subarray
for (int i = 0; i < n; i++) {
if (a[i] < 0)
len = max(len,
max(n - i - 1, i));
}
return len;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, -3, 2, 5, -6 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxLength(arr, N)
<< "\n";
int arr1[] = { 1, 2, 3, 4 };
N = sizeof(arr1) / sizeof(arr1[0]);
cout << maxLength(arr1, N)
<< "\n";
return 0;
}
Java
// Java implementation of the above approach
import java.util.Arrays;
class GFG{
// Function to find length of the
// longest subarray such that product
// of the subarray is negative
static int maxLength(int a[], int n)
{
int product = 1, len = -1;
// Check if product of complete
// array is negative
for(int i = 0; i < n; i++)
product *= a[i];
// Total product is already
// negative
if (product < 0)
return n;
// Find an index i such the a[i]
// is negative and compare length
// of both halfs excluding a[i] to
// find max length subarray
for(int i = 0; i < n; i++)
{
if (a[i] < 0)
len = Math.max(len,
Math.max(n - i - 1, i));
}
return len;
}
// Driver code
public static void main (String[] args)
{
// Given array arr[]
int arr[] = new int[]{ 1, 2, -3,
2, 5, -6 };
int N = arr.length;
System.out.println(maxLength(arr, N));
// Given array arr[]
int arr1[] = new int[]{ 1, 2, 3, 4 };
N = arr1.length;
System.out.println(maxLength(arr1, N));
}
}
// This code is contributed by Pratima Pandey
Python3
# Python3 implementation of the above approach # Function to find length of the # longest subarray such that product # of the subarray is negative def maxLength(a, n): product = 1 length = -1 # Check if product of complete # array is negative for i in range (n): product *= a[i] # Total product is already # negative if (product < 0): return n # Find an index i such the a[i] # is negative and compare length # of both halfs excluding a[i] to # find max length subarray for i in range (n): if (a[i] < 0): length = max(length, max(n - i - 1, i)) return length # Driver Code if __name__ == "__main__": arr = [1, 2, -3, 2, 5, -6] N = len(arr) print (maxLength(arr, N)) arr1 = [1, 2, 3, 4] N = len(arr1) print (maxLength(arr1, N)) # This code is contributed by Chitranayal
C#
// C# implementation of the above approach
using System;
class GFG{
// Function to find length of the
// longest subarray such that product
// of the subarray is negative
static int maxLength(int []a, int n)
{
int product = 1, len = -1;
// Check if product of complete
// array is negative
for(int i = 0; i < n; i++)
product *= a[i];
// Total product is already
// negative
if (product < 0)
return n;
// Find an index i such the a[i]
// is negative and compare length
// of both halfs excluding a[i] to
// find max length subarray
for(int i = 0; i < n; i++)
{
if (a[i] < 0)
len = Math.Max(len,
Math.Max(n - i - 1, i));
}
return len;
}
// Driver code
public static void Main(String[] args)
{
// Given array []arr
int []arr = new int[]{ 1, 2, -3,
2, 5, -6 };
int N = arr.Length;
Console.WriteLine(maxLength(arr, N));
// Given array []arr
int []arr1 = new int[]{ 1, 2, 3, 4 };
N = arr1.Length;
Console.WriteLine(maxLength(arr1, N));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find length of the
// longest subarray such that product
// of the subarray is negative
function maxLength(a, n)
{
let product = 1, len = -1;
// Check if product of complete
// array is negative
for(let i = 0; i < n; i++)
product *= a[i];
// Total product is already
// negative
if (product < 0)
return n;
// Find an index i such the a[i]
// is negative and compare length
// of both halfs excluding a[i] to
// find max length subarray
for(let i = 0; i < n; i++)
{
if (a[i] < 0)
len = Math.max(len,
Math.max(n - i - 1, i));
}
return len;
}
// Driver code
// Given array []arr
let arr = [ 1, 2, -3,
2, 5, -6 ];
let N = arr.length;
document.write(maxLength(arr, N) + "<br/>");
// Given array []arr
let arr1 = [ 1, 2, 3, 4 ];
N = arr1.Length;
document.write(maxLength(arr1, N) + "<br/>");
// This code is contributed by sanjoy_62.
</script>
Producción:
5 -1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)