Subarreglo de producto máximo | conjunto 3

Dado un arreglo A[] que contiene enteros positivos y negativos, encuentre el subarreglo de producto máximo.
Ejemplos: 
 

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

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

Input: A[] = { -2, -3, 0, -2, -40 }
Output: 80  // The subarray is {-2, -40}

La idea es recorrer la array de izquierda a derecha manteniendo dos variables minVal y maxVal que representan el valor mínimo y máximo del producto hasta el i-ésimo índice de la array. Ahora, si el i-ésimo elemento de la array es negativo, eso significa que ahora los valores de minVal y maxVal se intercambiarán ya que el valor de maxVal se volverá mínimo al multiplicarlo por un número negativo. Ahora, compare minVal y maxVal. 
El valor de minVal y maxVal depende del elemento de índice actual o del producto del elemento de índice actual y el minVal y maxVal anteriores, respectivamente.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find maximum product subarray
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum product subarray
int maxProduct(int* arr, int n)
{
    // Variables to store maximum and minimum
    // product till ith index.
    int minVal = arr[0];
    int maxVal = arr[0];
 
    int maxProduct = arr[0];
 
    for (int i = 1; i < n; i++) {
 
        // When multiplied by -ve number,
        // maxVal becomes minVal
        // and minVal becomes maxVal.
        if (arr[i] < 0)
            swap(maxVal, minVal);
 
        // maxVal and minVal stores the
        // product of subarray ending at arr[i].
        maxVal = max(arr[i], maxVal * arr[i]);
        minVal = min(arr[i], minVal * arr[i]);
 
        // Max Product of array.
        maxProduct = max(maxProduct, maxVal);
    }
 
    // Return maximum product found in array.
    return maxProduct;
}
 
// Driver Code
int main()
{
    int arr[] = { -1, -3, -10, 0, 60 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << "Maximum Subarray product is "
         << maxProduct(arr, n) << endl;
 
    return 0;
}

Java

// Java program to find maximum product subarray
import java.io.*;
 
class GFG {
 
    // Function to find maximum product subarray
    static int maxProduct(int arr[], int n)
    {
         
        // Variables to store maximum and minimum
        // product till ith index.
        int minVal = arr[0];
        int maxVal = arr[0];
     
        int maxProduct = arr[0];
     
        for (int i = 1; i < n; i++)
        {
     
            // When multiplied by -ve number,
            // maxVal becomes minVal
            // and minVal becomes maxVal.
            if (arr[i] < 0)
            {
                int temp = maxVal;
                maxVal = minVal;
                minVal =temp;
             
            }
     
            // maxVal and minVal stores the
            // product of subarray ending at arr[i].
            maxVal = Math.max(arr[i], maxVal * arr[i]);
            minVal = Math.min(arr[i], minVal * arr[i]);
     
            // Max Product of array.
            maxProduct = Math.max(maxProduct, maxVal);
        }
     
        // Return maximum product found in array.
        return maxProduct;
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int arr[] = { -1, -3, -10, 0, 60 };
        int n = arr.length;
     
        System.out.println( "Maximum Subarray product is "
                                    + maxProduct(arr, n));
    }
}
 
// This code is contributed by anuj_67.

Python3

# Python 3 program to find maximum
# product subarray
 
# Function to find maximum
# product subarray
def maxProduct(arr, n):
     
    # Variables to store maximum and
    # minimum product till ith index.
    minVal = arr[0]
    maxVal = arr[0]
 
    maxProduct = arr[0]
 
    for i in range(1, n, 1):
         
        # When multiplied by -ve number,
        # maxVal becomes minVal
        # and minVal becomes maxVal.
        if (arr[i] < 0):
            temp = maxVal
            maxVal = minVal
            minVal = temp
             
        # maxVal and minVal stores the
        # product of subarray ending at arr[i].
        maxVal = max(arr[i], maxVal * arr[i])
        minVal = min(arr[i], minVal * arr[i])
 
        # Max Product of array.
        maxProduct = max(maxProduct, maxVal)
 
    # Return maximum product
    # found in array.
    return maxProduct
 
# Driver Code
if __name__ == '__main__':
    arr = [-1, -3, -10, 0, 60]
 
    n = len(arr)
 
    print("Maximum Subarray product is",
                     maxProduct(arr, n))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to find
// maximum product subarray
using System;
 
class GFG
{
 
    // Function to find maximum
    // product subarray
    static int maxProduct(int []arr,
                          int n)
    {
         
        // Variables to store
        // maximum and minimum
        // product till ith index.
        int minVal = arr[0];
        int maxVal = arr[0];
     
        int maxProduct = arr[0];
     
        for (int i = 1; i < n; i++)
        {
     
            // When multiplied by -ve
            // number, maxVal becomes
            // minVal and minVal
            // becomes maxVal.
            if (arr[i] < 0)
            {
                int temp = maxVal;
                maxVal = minVal;
                minVal = temp;
             
            }
     
            // maxVal and minVal stores
            // the product of subarray
            // ending at arr[i].
            maxVal = Math.Max(arr[i],
                              maxVal * arr[i]);
            minVal = Math.Min(arr[i],
                              minVal * arr[i]);
     
            // Max Product of array.
            maxProduct = Math.Max(maxProduct,
                                  maxVal);
        }
     
        // Return maximum product
        // found in array.
        return maxProduct;
    }
     
    // Driver Code
    public static void Main ()
    {
        int []arr = {-1, -3, -10, 0, 60};
        int n = arr.Length;
     
        Console.WriteLine("Maximum Subarray " +
                                "product is " +
                           maxProduct(arr, n));
    }
}
 
// This code is contributed by anuj_67.

PHP

<?php
// PHP program to find maximum
// product subarray
 
// Function to find maximum
// product subarray
function maxProduct(&$arr, $n)
{
    // Variables to store maximum and
    // minimum product till ith index.
    $minVal = $arr[0];
    $maxVal = $arr[0];
 
    $maxProduct = $arr[0];
 
    for ($i = 1; $i < $n; $i++)
    {
 
        // When multiplied by -ve number,
        // maxVal becomes minVal
        // and minVal becomes maxVal.
        if ($arr[$i] < 0)
        {
            $temp = $maxVal;
            $maxVal = $minVal;
            $minVal = $temp;
        }
 
        // maxVal and minVal stores the
        // product of subarray ending at arr[i].
        $maxVal = max($arr[$i], $maxVal * $arr[$i]);
        $minVal = min($arr[$i], $minVal * $arr[$i]);
 
        // Max Product of array.
        $maxProduct = max($maxProduct, $maxVal);
    }
 
    // Return maximum product found in array.
    return $maxProduct;
}
 
// Driver Code
$arr = array( -1, -3, -10, 0, 60 );
$n = sizeof($arr);
echo "Maximum Subarray product is " .
         maxProduct($arr, $n) . "\n";
 
// This code is contributed by ita_c
?>

Javascript

<script>
// Javascript program to find maximum product subarray
     
    // Function to find maximum product subarray
    function maxProduct(arr,n)
    {
        // Variables to store maximum and minimum
        // product till ith index.
        let minVal = arr[0];
        let maxVal = arr[0];
       
        let maxProduct = arr[0];
       
        for (let i = 1; i < n; i++)
        {
       
            // When multiplied by -ve number,
            // maxVal becomes minVal
            // and minVal becomes maxVal.
            if (arr[i] < 0)
            {
                let temp = maxVal;
                maxVal = minVal;
                minVal =temp;
               
            }
       
            // maxVal and minVal stores the
            // product of subarray ending at arr[i].
            maxVal = Math.max(arr[i], maxVal * arr[i]);
            minVal = Math.min(arr[i], minVal * arr[i]);
       
            // Max Product of array.
            maxProduct = Math.max(maxProduct, maxVal);
        }
       
        // Return maximum product found in array.
        return maxProduct;
    }
     
     // Driver Code
    let arr=[ -1, -3, -10, 0, 60 ];
    let n = arr.length;
    document.write( "Maximum Subarray product is "
                                    + maxProduct(arr, n));
     
 
// This code is contributed by rag2127
</script>
Producción: 

Maximum Sub array product is 60

 

Complejidad de Tiempo : O( n ) 
Espacio Auxiliar : O( 1 )
Artículos Relacionados
 

Publicación traducida automáticamente

Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *