Programa Javascript para Subarreglo Máximo de Producto

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[] = {-2, -40, 0, -2, -3}
Output:   80  // The subarray is {-2, -40}

Solución ingenua:

La idea es recorrer todos los subarreglos contiguos, encontrar el producto de cada uno de estos subarreglos y devolver el producto máximo de estos resultados.

A continuación se muestra la implementación del enfoque anterior.

<script>
  
// Javascript program to find Maximum Product Subarray
  
/* Returns the product of max product subarray.*/
function maxSubarrayProduct(arr, n)
{
    // Initializing result
    let result = arr[0];
  
    for (let i = 0; i < n; i++) 
    {
        let mul = arr[i];
        // traversing in current subarray
        for (let j = i + 1; j < n; j++) 
        {
            // updating result every time
            // to keep an eye over the maximum product
            result = Math.max(result, mul);
            mul *= arr[j];
        }
        // updating the result for (n-1)th index.
        result = Math.max(result, mul);
    }
    return result;
}
  
// Driver code
  
    let arr = [ 1, -2, -3, 0, 7, -8, -2 ];
    let n = arr.length;
    document.write("Maximum Sub array product is "
        + maxSubarrayProduct(arr, n));
      
  
// This code is contributed by Mayank Tyagi
  
</script>

Producción:

Maximum Sub array product is 112

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Solución eficiente:

La siguiente solución asume que la array de entrada dada siempre tiene una salida positiva. La solución funciona para todos los casos mencionados anteriormente. No funciona para arreglos como {0, 0, -20, 0}, {0, 0, 0}… etc. La solución se puede modificar fácilmente para manejar este caso. 
Es similar al problema de subarreglo contiguo de suma más grande . Lo único que se debe tener en cuenta aquí es que el producto máximo también se puede obtener mediante el producto mínimo (negativo) que termina con el elemento anterior multiplicado por este elemento. Por ejemplo, en el arreglo {12, 2, -3, -5, -6, -2}, cuando estamos en el elemento -2, el producto máximo es la multiplicación del producto mínimo que termina en -6 y -2. 

<script>
  
// JavaScript program to find 
// Maximum Product Subarray
  
/* Returns the product 
  of max product subarray.
Assumes that the given 
array always has a subarray
with product more than 1 */
function maxSubarrayProduct(arr, n)
{
    // max positive product 
    // ending at the current position
    let max_ending_here = 1;
  
    // min negative product ending 
    // at the current position
    let min_ending_here = 1;
  
    // Initialize overall max product
    let max_so_far = 0;
    let flag = 0;
    /* Traverse through the array. 
    Following values are
    maintained after the i'th iteration:
    max_ending_here is always 1 or 
    some positive product ending with arr[i]
    min_ending_here is always 1 or 
    some negative product ending with arr[i] */
    for (let i = 0; i < n; i++)
    {
        /* If this element is positive, update
        max_ending_here. Update min_ending_here only if
        min_ending_here is negative */
        if (arr[i] > 0) 
        {
            max_ending_here = max_ending_here * arr[i];
            min_ending_here
                = Math.min(min_ending_here * arr[i], 1);
            flag = 1;
        }
  
        /* If this element is 0, then the maximum product
        cannot end here, make both max_ending_here and
        min_ending_here 0
        Assumption: Output is alway greater than or equal
                    to 1. */
        else if (arr[i] == 0) {
            max_ending_here = 1;
            min_ending_here = 1;
        }
  
        /* If element is negative. This is tricky
         max_ending_here can either be 1 or positive.
         min_ending_here can either be 1 or negative.
         next max_ending_here will always be prev.
         min_ending_here * arr[i] ,next min_ending_here
         will be 1 if prev max_ending_here is 1, otherwise
         next min_ending_here will be prev max_ending_here *
         arr[i] */
  
        else {
            let temp = max_ending_here;
            max_ending_here
                = Math.max(min_ending_here * arr[i], 1);
            min_ending_here = temp * arr[i];
        }
  
        // update max_so_far, if needed
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
    }
    if (flag == 0 && max_so_far == 0)
        return 0;
    return max_so_far;
}
  
  
    // Driver program 
      
    let arr = [ 1, -2, -3, 0, 7, -8, -2 ];
    let n = arr.length;
    document.write("Maximum Sub array product is " + 
                    maxSubarrayProduct(arr,n)); 
      
</script>

Maximum Sub array product is 112

Complejidad temporal: O(n) 
Espacio auxiliar: O(1)

Consulte el artículo completo sobre el subarreglo máximo de productos para obtener más detalles.