Dado un arreglo arr[] que consta de N enteros, la tarea es imprimir la longitud del subarreglo más largo con un producto positivo.
Ejemplos:
Entrada: array[] ={0, 1, -2, -3, -4}
Salida: 3
Explicación:
El subarreglo más largo con productos positivos es: {1, -2, -3}. Por lo tanto, la longitud requerida es 3.Entrada: array[]={-1, -2, 0, 1, 2}
Salida: 2
Explicación:
El subarreglo más largo con productos positivos es: {-1, -2}, {1, 2}. Por lo tanto, la longitud requerida es 2.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles y verificar si su producto es positivo o no. Entre todos esos subarreglos, imprima la longitud del subarreglo más largo obtenido.
Complejidad de Tiempo: (N 3 )
Espacio Auxiliar: O(1)
Enfoque Eficiente: El problema se puede resolver usando Programación Dinámica. La idea aquí es mantener el conteo de elementos positivos y elementos negativos para que su producto sea positivo. Siga los pasos a continuación para resolver el problema:
- Inicialice la variable, digamos res , para almacenar la longitud del subarreglo más largo con el producto positivo.
- Inicialice dos variables, Pos y Neg , para almacenar la longitud del subarreglo actual con los productos positivo y negativo respectivamente.
- Iterar sobre la array.
- Si arr[i] = 0: restablecer el valor de Pos y Neg .
- Si arr[i] > 0: Incremente Pos en 1. Si al menos un elemento está presente en el subarreglo con el producto negativo, entonces incremente Neg en 1.
- Si arr[i] < 0: Intercambie Pos y Neg e incremente Neg en 1. Si al menos un elemento está presente en el subarreglo con el producto positivo, entonces incremente Pos también.
- Actualice res=max(res, Pos).
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of
// longest subarray whose product
// is positive
int maxLenSub(int arr[], int N)
{
// Stores the length of current
// subarray with positive product
int Pos = 0;
// Stores the length of current
// subarray with negative product
int Neg = 0;
// Stores the length of the longest
// subarray with positive product
int res = 0;
for (int i = 0; i < N; i++) {
if (arr[i] == 0) {
// Reset the value
Pos = Neg = 0;
}
// If current element is positive
else if (arr[i] > 0) {
// Increment the length of
// subarray with positive product
Pos += 1;
// If at least one element is
// present in the subarray with
// negative product
if (Neg != 0) {
Neg += 1;
}
// Update res
res = max(res, Pos);
}
// If current element is negative
else {
swap(Pos, Neg);
// Increment the length of subarray
// with negative product
Neg += 1;
// If at least one element is present
// in the subarray with positive product
if (Pos != 0) {
Pos += 1;
}
// Update res
res = max(res, Pos);
}
}
return res;
}
// Driver Code
int main()
{
int arr[] = { -1, -2, -3, 0, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxLenSub(arr, N);
}
Python3
# Python3 program to implement # the above approach # Function to find the length of # longest subarray whose product # is positive def maxLenSub(arr, N): # Stores the length of current # subarray with positive product Pos = 0 # Stores the length of current # subarray with negative product Neg = 0 # Stores the length of the longest # subarray with positive product res = 0 for i in range(N): if (arr[i] == 0): # Reset the value Pos = Neg = 0 # If current element is positive elif (arr[i] > 0): # Increment the length of # subarray with positive product Pos += 1 # If at least one element is # present in the subarray with # negative product if (Neg != 0): Neg += 1 # Update res res = max(res, Pos) # If current element is negative else: Pos, Neg = Neg, Pos # Increment the length of subarray # with negative product Neg += 1 # If at least one element is present # in the subarray with positive product if (Pos != 0): Pos += 1 # Update res res = max(res, Pos) return res # Driver Code if __name__ == '__main__': arr = [ -1, -2, -3, 0, 1 ] N = len(arr) print(maxLenSub(arr, N)) # This code is contributed by mohit kumar 29
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the length of
// longest subarray whose product
// is positive
static int maxLenSub(int arr[], int N)
{
// Stores the length of current
// subarray with positive product
int Pos = 0;
// Stores the length of current
// subarray with negative product
int Neg = 0;
// Stores the length of the longest
// subarray with positive product
int res = 0;
for (int i = 0; i < N; i++)
{
if (arr[i] == 0)
{
// Reset the value
Pos = Neg = 0;
}
// If current element is positive
else if (arr[i] > 0)
{
// Increment the length of
// subarray with positive product
Pos += 1;
// If at least one element is
// present in the subarray with
// negative product
if (Neg != 0)
{
Neg += 1;
}
// Update res
res = Math.max(res, Pos);
}
// If current element is negative
else
{
Pos = Pos + Neg;
Neg = Pos - Neg;
Pos = Pos - Neg;
// Increment the length of subarray
// with negative product
Neg += 1;
// If at least one element is present
// in the subarray with positive product
if (Pos != 0)
{
Pos += 1;
}
// Update res
res = Math.max(res, Pos);
}
}
return res;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {-1, -2, -3, 0, 1};
int N = arr.length;
System.out.print(maxLenSub(arr, N));
}
}
// This code is contributed by Rajput-Ji
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the length of
// longest subarray whose product
// is positive
static int maxLenSub(int[] arr, int N)
{
// Stores the length of current
// subarray with positive product
int Pos = 0;
// Stores the length of current
// subarray with negative product
int Neg = 0;
// Stores the length of the longest
// subarray with positive product
int res = 0;
for (int i = 0; i < N; i++)
{
if (arr[i] == 0)
{
// Reset the value
Pos = Neg = 0;
}
// If current element is positive
else if (arr[i] > 0)
{
// Increment the length of
// subarray with positive product
Pos += 1;
// If at least one element is
// present in the subarray with
// negative product
if (Neg != 0)
{
Neg += 1;
}
// Update res
res = Math.Max(res, Pos);
}
// If current element is negative
else
{
Pos = Pos + Neg;
Neg = Pos - Neg;
Pos = Pos - Neg;
// Increment the length of subarray
// with negative product
Neg += 1;
// If at least one element is present
// in the subarray with positive product
if (Pos != 0)
{
Pos += 1;
}
// Update res
res = Math.Max(res, Pos);
}
}
return res;
}
// Driver Code
public static void Main()
{
int[] arr = {-1, -2, -3, 0, 1};
int N = arr.Length;
Console.Write(maxLenSub(arr, N));
}
}
// This code is contributed by Chitranayal
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the length of
// longest subarray whose product
// is positive
function maxLenSub(arr, N)
{
// Stores the length of current
// subarray with positive product
var Pos = 0;
// Stores the length of current
// subarray with negative product
var Neg = 0;
// Stores the length of the longest
// subarray with positive product
var res = 0;
for (var i = 0; i < N; i++) {
if (arr[i] == 0) {
// Reset the value
Pos = Neg = 0;
}
// If current element is positive
else if (arr[i] > 0) {
// Increment the length of
// subarray with positive product
Pos += 1;
// If at least one element is
// present in the subarray with
// negative product
if (Neg != 0) {
Neg += 1;
}
// Update res
res = Math.max(res, Pos);
}
// If current element is negative
else {
[Pos, Neg] = [Neg, Pos];
// Increment the length of subarray
// with negative product
Neg += 1;
// If at least one element is present
// in the subarray with positive product
if (Pos != 0) {
Pos += 1;
}
// Update res
res = Math.max(res, Pos);
}
}
return res;
}
// Driver Code
var arr = [-1, -2, -3, 0, 1];
var N = arr.length;
document.write( maxLenSub(arr, N));
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA