Subarreglo de producto máximo | Conjunto 2 (usando dos transversales)

Dada una array que contiene enteros positivos y negativos, encuentre el producto del subarreglo de producto máximo. La complejidad del tiempo esperado es O(n) y solo se puede usar O(1) espacio extra.

Ejemplos: 

Input: arr[] = {6, -3, -10, 0, 2}
Output:   180  // The subarray is {6, -3, -10}

Input: arr[] = {-1, -3, -10, 0, 60}
Output:   60  // The subarray is {60}

Input: arr[] = {-1, -2, -3, 4}
Output:   24  // The subarray is {-2, -3, 4}

Input: arr[] = {-10}
Output:   0  // An empty array is also subarray
             // and product of empty subarray is
             // considered as 0.

Hemos discutido una solución a este problema aquí . 
En este post se discute una solución interesante. La idea se basa en el hecho de que el producto máximo general es el máximo de los dos siguientes: 

1. Producto máximo en recorrido de izquierda a derecha.
2. Producto máximo en recorrido de derecha a izquierda

Por ejemplo, considere la entrada de la tercera muestra anterior {-1, -2, -3, 4}. Si recorremos la array solo hacia adelante (considerando -1 como parte de la salida), el producto máximo será 2. Si recorremos la array hacia atrás (considerando 4 como parte de la salida), el producto máximo será 24, es decir; {-2, -3, 4}. 
Una cosa importante es manejar 0’s. Necesitamos calcular una nueva suma hacia adelante (o hacia atrás) cada vez que veamos 0.

A continuación se muestra la implementación de la idea anterior: 

// C++ program to find maximum product subarray
#include<bits/stdc++.h>
using namespace std;
 
// Function for maximum product
int max_product(int arr[], int n)
{
    // Initialize maximum products in forward and
    // backward directions
    int max_fwd = INT_MIN, max_bkd = INT_MIN;
 
    // Initialize current product
    int max_till_now = 1;
 
    //check if zero is present in an array or not
    bool isZero=false;
     
    // max_fwd for maximum contiguous product in
    // forward direction
    // max_bkd for maximum contiguous product in
    // backward direction
    // iterating within forward direction in array
    for (int i=0; i<n; i++)
    {
        // if arr[i]==0, it is breaking condition
        // for contiguous subarray
        max_till_now = max_till_now*arr[i];
        if (max_till_now == 0)
        {  
             isZero=true;
             max_till_now = 1;
            continue;
        }
        if (max_fwd < max_till_now) // update max_fwd
            max_fwd = max_till_now;
    }
 
     max_till_now = 1;
 
    // iterating within backward direction in array
    for (int i=n-1; i>=0; i--)
    {
        max_till_now = max_till_now * arr[i];
        if (max_till_now == 0)
        {
            isZero=true;
            max_till_now = 1;
            continue;
        }
 
        // update max_bkd
        if (max_bkd < max_till_now)
            max_bkd = max_till_now;
    }
 
    // return max of max_fwd and max_bkd
    int res =  max(max_fwd, max_bkd);
 
    // Product should not be negative.
    // (Product of an empty subarray is
    // considered as 0)
    if(isZero)
    return max(res, 0);
 
    return res;
}
 
// Driver Program to test above function
int main()
{
    int arr[] = {-1, -2, -3, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << max_product(arr, n) << endl;
    return 0;
}

// Java program to find
// maximum product subarray
import java.io.*;
 
class GFG
{
 
// Function for maximum product
static int max_product(int arr[], int n)
{
    // Initialize maximum products in
    // forward and backward directions
    int max_fwd = Integer.MIN_VALUE,
        max_bkd = Integer.MIN_VALUE;
 
    //check if zero is present in an array or not
    boolean isZero=false;
 
    // Initialize current product
    int max_till_now = 1;
 
    // max_fwd for maximum contiguous
    // product in forward direction
    // max_bkd for maximum contiguous
    // product in backward direction
    // iterating within forward
    // direction in array
    for (int i = 0; i < n; i++)
    {
        // if arr[i]==0, it is breaking
        // condition for contiguous subarray
        max_till_now = max_till_now * arr[i];
        if (max_till_now == 0)
        {
            isZero=true;
            max_till_now = 1;
            continue;
        }
         
        // update max_fwd
        if (max_fwd < max_till_now)
            max_fwd = max_till_now;
    }
 
    max_till_now = 1;
 
    // iterating within backward
    // direction in array
    for (int i = n - 1; i >= 0; i--)
    {
        max_till_now = max_till_now * arr[i];
        if (max_till_now == 0)
        {
            isZero=true;
            max_till_now = 1;
            continue;
        }
 
        // update max_bkd
        if (max_bkd < max_till_now)
            max_bkd = max_till_now;
    }
 
    // return max of max_fwd and max_bkd
    int res = Math. max(max_fwd, max_bkd);
 
    // Product should not be negative.
    // (Product of an empty subarray is
    // considered as 0)
    if(isZero)
    return Math.max(res, 0);
     
    return res;
}
 
// Driver Code
public static void main (String[] args)
{
    int arr[] = {-1, -2, -3, 4};
    int n = arr.length;
    System.out.println( max_product(arr, n) );
}
}
 
// This code is contributed by anuj_67.

# Python3 program to find
# maximum product subarray
import sys
 
# Function for maximum product
def max_product(arr, n):
 
    # Initialize maximum products
    # in forward and backward directions
    max_fwd = -sys.maxsize - 1
    max_bkd = -sys.maxsize - 1
     
    #check if zero is present in an array or not
    isZero=False;
 
    # Initialize current product
    max_till_now = 1
 
    # max_fwd for maximum contiguous
    # product in forward direction
    # max_bkd for maximum contiguous
    # product in backward direction
    # iterating within forward
    # direction in array
    for i in range(n):
     
        # if arr[i]==0, it is breaking
        # condition for contiguous subarray
        max_till_now = max_till_now * arr[i]
        if (max_till_now == 0):
            isZero=True
            max_till_now = 1;
            continue
         
        if (max_fwd < max_till_now): #update max_fwd
            max_fwd = max_till_now
     
    max_till_now = 1
 
    # iterating within backward
    # direction in array
    for i in range(n - 1, -1, -1):
        max_till_now = max_till_now * arr[i]
         
        if (max_till_now == 0):
            isZero=True
            max_till_now = 1
            continue
 
        # update max_bkd
        if (max_bkd < max_till_now) :
            max_bkd = max_till_now
 
    # return max of max_fwd and max_bkd
    res = max(max_fwd, max_bkd)
 
    # Product should not be negative.
    # (Product of an empty subarray is
    # considered as 0)
    if isZero==True :
        return max(res, 0)
 
    return res
 
# Driver Code
arr = [-1, -2, -3, 4]
n = len(arr)
print(max_product(arr, n))
 
# This code is contributed
# by Yatin Gupta

// C# program to find maximum product
// subarray
using System;
 
class GFG {
 
    // Function for maximum product
    static int max_product(int []arr, int n)
    {
         
        // Initialize maximum products in
        // forward and backward directions
        int max_fwd = int.MinValue,
            max_bkd = int.MinValue;
     
        // Initialize current product
        int max_till_now = 1;
     
        // max_fwd for maximum contiguous
        // product in forward direction
        // max_bkd for maximum contiguous
        // product in backward direction
        // iterating within forward
        // direction in array
        for (int i = 0; i < n; i++)
        {
             
            // if arr[i]==0, it is breaking
            // condition for contiguous subarray
            max_till_now = max_till_now * arr[i];
             
            if (max_till_now == 0)
            {
                max_till_now = 1;
                continue;
            }
             
            // update max_fwd
            if (max_fwd < max_till_now)
                max_fwd = max_till_now;
        }
     
        max_till_now = 1;
     
        // iterating within backward
        // direction in array
        for (int i = n - 1; i >= 0; i--)
        {
            max_till_now = max_till_now * arr[i];
            if (max_till_now == 0)
            {
                max_till_now = 1;
                continue;
            }
     
            // update max_bkd
            if (max_bkd < max_till_now)
                max_bkd = max_till_now;
        }
     
        // return max of max_fwd and max_bkd
        int res = Math. Max(max_fwd, max_bkd);
     
        // Product should not be negative.
        // (Product of an empty subarray is
        // considered as 0)
        return Math.Max(res, 0);
    }
     
    // Driver Code
    public static void Main ()
    {
        int []arr = {-1, -2, -3, 4};
        int n = arr.Length;
         
        Console.Write( max_product(arr, n) );
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP program to find maximum
// product subarray
 
// Function for maximum product
function max_product( $arr, $n)
{
     
    // Initialize maximum products
    // in forward and backward
    // directions
    $max_fwd = PHP_INT_MIN;
    $max_bkd = PHP_INT_MIN;
 
    // Initialize current product
    $max_till_now = 1;
 
    // max_fwd for maximum contiguous
    // product in forward direction
    // max_bkd for maximum contiguous
    // product in backward direction
    // iterating within forward direction
    // in array
    for ($i = 0; $i < $n; $i++)
    {
         
        // if arr[i]==0, it is
        // breaking condition
        // for contiguous subarray
        $max_till_now = $max_till_now * $arr[$i];
        if ($max_till_now == 0)
        {
            $max_till_now = 1;
            continue;
        }
         
        // update max_fwd
        if ($max_fwd < $max_till_now)
            $max_fwd = $max_till_now;
    }
 
    $max_till_now = 1;
 
    // iterating within backward
    // direction in array
    for($i = $n - 1; $i >= 0; $i--)
    {
        $max_till_now = $max_till_now * $arr[$i];
        if ($max_till_now == 0)
        {
            $max_till_now = 1;
            continue;
        }
 
        // update max_bkd
        if ($max_bkd < $max_till_now)
            $max_bkd = $max_till_now;
    }
 
    // return max of max_fwd
    // and max_bkd
    $res = max($max_fwd, $max_bkd);
 
    // Product should not be negative.
    // (Product of an empty subarray is
    // considered as 0)
    return max($res, 0);
}
 
    // Driver Code
    $arr = array(-1, -2, -3, 4);
    $n = count($arr);
    echo max_product($arr, $n);
 
// This code is contributed by anuj_67.
?>

<script>
 
    // JavaScript program to find maximum product
    // subarray
     
    // Function for maximum product
    function max_product(arr, n)
    {
           
        // Initialize maximum products in
        // forward and backward directions
        let max_fwd = Number.MIN_VALUE,
            max_bkd = Number.MIN_VALUE;
       
        // Initialize current product
        let max_till_now = 1;
       
        // max_fwd for maximum contiguous
        // product in forward direction
        // max_bkd for maximum contiguous
        // product in backward direction
        // iterating within forward
        // direction in array
        for (let i = 0; i < n; i++)
        {
               
            // if arr[i]==0, it is breaking
            // condition for contiguous subarray
            max_till_now = max_till_now * arr[i];
               
            if (max_till_now == 0)
            {
                max_till_now = 1;
                continue;
            }
               
            // update max_fwd
            if (max_fwd < max_till_now)
                max_fwd = max_till_now;
        }
       
        max_till_now = 1;
       
        // iterating within backward
        // direction in array
        for (let i = n - 1; i >= 0; i--)
        {
            max_till_now = max_till_now * arr[i];
            if (max_till_now == 0)
            {
                max_till_now = 1;
                continue;
            }
       
            // update max_bkd
            if (max_bkd < max_till_now)
                max_bkd = max_till_now;
        }
       
        // return max of max_fwd and max_bkd
        let res = Math.max(max_fwd, max_bkd);
       
        // Product should not be negative.
        // (Product of an empty subarray is
        // considered as 0)
        return Math.max(res, 0);
    }
     
    let arr = [-1, -2, -3, 4];
    let n = arr.length;
 
    document.write(max_product(arr, n) );
     
</script>

24

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(1)

Tenga en cuenta que la solución anterior requiere dos recorridos de una array, mientras que la solución anterior requiere solo un recorrido.
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.