Programa Java para el subarreglo máximo de productos

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.

// Java program to find maximum product subarray
import java.io.*;
  
class GFG {
    /* Returns the product of max product subarray.*/
    static int maxSubarrayProduct(int arr[])
    {
        // Initializing result
        int result = arr[0];
        int n = arr.length;
  
        for (int i = 0; i < n; i++)
        {
            int mul = arr[i];
            // traversing in current subarray
            for (int 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
    public static void main(String[] args)
    {
        int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
        System.out.println("Maximum Sub array product is "
                           + maxSubarrayProduct(arr));
    }
}
  
// This code is contributed by yashbeersingh42

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. 

// Java program to find maximum product subarray
import java.io.*;
  
class ProductSubarray {
  
    // Utility functions to get 
    // minimum of two integers
    static int min(int x, int y) { 
    return x < y ? x : y; 
    }
  
    // Utility functions to get 
    // maximum of two integers
    static int max(int x, int y) { 
    return x > y ? x : y;
    }
  
    /* Returns the product of 
    max product subarray.
    Assumes that the given 
    array always has a subarray
    with product more than 1 */
    static int maxSubarrayProduct(int arr[])
    {
        int n = arr.length;
        // max positive product 
        // ending at the current
        // position
        int max_ending_here = 1;
  
        // min negative product 
        // ending at the current
        // position
        int min_ending_here = 1;
  
        // Initialize overall max product
        int max_so_far = 0;
        int flag = 0;
  
        /* Traverse through the array. Following
        values are maintained after the ith 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 (int 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
                    = 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 min_ending_here will always be prev.
            max_ending_here * arr[i]
            next max_ending_here will be 1 if prev
            min_ending_here is 1, otherwise
            next max_ending_here will be
                        prev min_ending_here * arr[i] */
            else {
                int temp = max_ending_here;
                max_ending_here
                    = 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 Code
    public static void main(String[] args)
    {
  
        int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
        System.out.println("Maximum Sub array product is "
                        + maxSubarrayProduct(arr));
    }
} /*This code is contributed by Devesh Agrawal*/

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.