Dado un arreglo arr[] de N enteros, la tarea es encontrar la longitud del subarreglo más largo cuyo producto sea mayor o igual a 0.
Ejemplos:
Entrada: arr[] = {-1, 1, 1, -2, 3, 2, -1 }
Salida: 6
Explicación:
El subarreglo más largo con producto ≥ 0 = {1, 1, -2, 3, 2, – 1} y {-1, 1, 1, -2, 3, 2}.
Longitud de cada uno = 6.Entrada: arr[] = {-1, -2, -3, -4}
Salida: 4
Explicación:
El subarreglo más largo con producto ≥ 0 = {-1, -2, -3, -4}.
Longitud = 4.
Acercarse:
- Comprueba si el producto de todos los elementos de la array dada es mayor o igual a cero o no.
- En caso afirmativo, la longitud del subarreglo más largo con un producto mayor o igual a cero es la longitud del arreglo .
- Si la declaración anterior no es cierta, entonces la array contiene un número impar de elementos negativos. En este caso, para encontrar el subarreglo más largo, haga lo siguiente:
- Para cada elemento negativo que aparece en el arreglo, el subarreglo a la izquierda y a la derecha del elemento actual da el producto que es mayor o igual a 0. Por lo tanto, la longitud del subarreglo más largo requerido será:
L = max(L, max(i, N - i - 1))
- Siga actualizando la longitud del subarreglo para cada elemento negativo que se encuentre en el arreglo.
- El valor de L es la longitud del subarreglo más largo con un producto mayor que igual a 0.
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 that count the length
// of longest subarray with product
// greater than or equals to zero
int maxLength(int arr[], int N)
{
int product = 1, len = 0;
for (int i = 0; i < N; i++) {
product *= arr[i];
}
// If product is greater than
// zero, return array size
if (product >= 0) {
return N;
}
// Traverse the array and if
// any negative element found
// then update the length of
// longest subarray with the
// length of left and right subarray
for (int i = 0; i < N; i++) {
if (arr[i] < 0) {
len = max(len,
max(N - i - 1, i));
}
}
return len;
}
// Driver Code
int main()
{
int arr[] = { -1, 1, 1, -2, 3, 2, -1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxLength(arr, N) << endl;
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
public class GFG{
// Function that count the length
// of longest subarray with product
// greater than or equals to zero
static int maxLength(int arr[], int N)
{
int product = 1, len = 0;
for (int i = 0; i < N; i++) {
product *= arr[i];
}
// If product is greater than
// zero, return array size
if (product >= 0) {
return N;
}
// Traverse the array and if
// any negative element found
// then update the length of
// longest subarray with the
// length of left and right subarray
for (int i = 0; i < N; i++) {
if (arr[i] < 0) {
len = Math.max(len, Math.max(N - i - 1, i));
}
}
return len;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { -1, 1, 1, -2, 3, 2, -1 };
int N = arr.length;
System.out.println(maxLength(arr, N));
}
}
// This code is contributed by AbhiThakur
Python3
# Python3 implementation of the above approach # Function that count the Length # of longest subarray with product # greater than or equals to zero def maxLength(arr, N): product = 1 Len = 0 for i in arr: product *= i # If product is greater than # zero, return array size if (product >= 0): return N # Traverse the array and if # any negative element found # then update the Length of # longest subarray with the # Length of left and right subarray for i in range(N): if (arr[i] < 0): Len = max(Len,max(N - i - 1, i)) return Len # Driver Code if __name__ == '__main__': arr = [-1, 1, 1, -2, 3, 2, -1] N = len(arr) print(maxLength(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the above approach
using System;
class GFG{
// Function that count the length
// of longest subarray with product
// greater than or equals to zero
static int maxLength(int []arr, int N)
{
int product = 1, len = 0;
for (int i = 0; i < N; i++) {
product *= arr[i];
}
// If product is greater than
// zero, return array size
if (product >= 0) {
return N;
}
// Traverse the array and if
// any negative element found
// then update the length of
// longest subarray with the
// length of left and right subarray
for (int i = 0; i < N; i++) {
if (arr[i] < 0) {
len = Math.Max(len, Math.Max(N - i - 1, i));
}
}
return len;
}
// Driver Code
public static void Main()
{
int []arr = { -1, 1, 1, -2, 3, 2, -1 };
int N = arr.Length;
Console.WriteLine(maxLength(arr, N));
}
}
// This code is contributed by abhaysingh290895
Javascript
<script>
// Javascript implementation of the above approach
// Function that count the length
// of longest subarray with product
// greater than or equals to zero
function maxLength(arr, N)
{
var product = 1, len = 0;
for (var i = 0; i < N; i++) {
product *= arr[i];
}
// If product is greater than
// zero, return array size
if (product >= 0) {
return N;
}
// Traverse the array and if
// any negative element found
// then update the length of
// longest subarray with the
// length of left and right subarray
for (var i = 0; i < N; i++) {
if (arr[i] < 0) {
len = Math.max(len,
Math.max(N - i - 1, i));
}
}
return len;
}
// Driver Code
var arr = [ -1, 1, 1, -2, 3, 2, -1 ];
var N = arr.length;
document.write(maxLength(arr, N));
// This code is contributed by rutvik_56.
</script>
Producción:
6
Complejidad de tiempo: O(N) , donde N es la longitud de la array.
Espacio Auxiliar: O(1)