Maximum Product Subarray

+10

Multiplica entre sí los elementos de un subarreglo de nums y devuelve el mayor producto que puede dar cualquier subarreglo. Un subarreglo contiene elementos consecutivos, sin espacios, y nunca está vacío, así que incluso un arreglo de números negativos tiene una respuesta. Se permiten ceros y valores negativos.

Función

maxProduct(nums: integer-array) → integer

numsinteger-array: los enteros que se van a multiplicar, cada uno entre -10 y 10
Devuelveinteger: el mayor producto de un subarreglo no vacío

Restricciones

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
El producto de cada subarreglo cabe en un entero con signo de 32 bits.

Ejemplos

Entrada: nums = [2, -5, 3, -2, 0, 4]
Salida: 60
Explicación: Los dos negativos se cancelan: 2 × -5 × 3 × -2 = 60. El 0 divide el arreglo en dos, y el 4 del otro lado no puede superar 60.

Entrada: nums = [-2, 3, -4, -1]
Salida: 24
Explicación: El producto de todo el arreglo es -24 porque contiene tres números negativos. Al omitir el último elemento, quedan dos: -2 × 3 × -4 = 24, que supera el 12 que obtienes al omitir el primer elemento.

Entrada: nums = [-6, 0, -7]
Salida: 0
Explicación: Un subarreglo que evita el 0 es un único número negativo, y un subarreglo que contiene el 0 da como producto 0. La mejor opción es el subarreglo [0].

Para ir más allá

¿Cómo podrías indicar también dónde empieza y termina el mejor subarreglo, manteniendo un tiempo de O(n) y un espacio de O(1)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Multiplicar por un número negativo invierte el orden de los productos, así que el producto más pequeño hasta el momento puede convertirse en el más grande en el siguiente paso, y un cero anula todos los productos. Guarda dos valores en cada índice en lugar de uno: el producto más grande y el más pequeño de un subarreglo que termina allí, y bastará con una sola pasada.

Multiplica cada subarreglo desde cada inicio

Correcto, pero no termina con las pruebas más grandes

Intuición

Fija un índice de inicio y mueve el final hacia la derecha, multiplicando un product acumulado por cada elemento nuevo. Compararlo con el mejor resultado después de cada paso cubre cada subarreglo una vez. Inicia best con nums[0], ya que la respuesta puede ser negativa.

Hay aproximadamente n²/2 pares de inicio y final, con una multiplicación cada uno: 2 × 10^8 para 20,000 elementos.

Algoritmo

Establece best en nums[0].
Para cada start, establece product en 1.
Mueve end desde start hasta el último índice y multiplica product por nums[end].
Si product es mayor que best, guárdalo.
Devuelve best.

def maxProduct(nums):
    n = len(nums)
    best = nums[0]
    for start in range(n):
        product = 1
        for end in range(start, n):
            # product is now the product of nums[start..end]
            product *= nums[end]
            if product > best:
                best = product
    return best

Recorre desde ambos extremos, reiniciando en los ceros

Intuición

Los ceros dividen el arreglo en segmentos sin ceros. Dentro de un segmento, todos los valores tienen un valor absoluto de al menos 1, así que un subarreglo más largo nunca tiene un producto absoluto menor; solo cambia el signo. Si hay un número par de negativos, lo mejor es tomar todo el segmento. Si hay un número impar, hay que quitar un negativo, y el mejor corte elimina el primer negativo y todo lo que hay antes de él, o el último negativo y todo lo que hay después de él. En cualquier caso, conservas un sufijo o un prefijo del segmento.

Un recorrido de izquierda a derecha con un producto acumulado comprueba cada prefijo y lo reinicia a 1 después de un 0. Un recorrido de derecha a izquierda comprueba cada sufijo. En [-2, 3, -4, -1], el recorrido de izquierda a derecha obtiene -2, -6, 24 y -24; el de derecha a izquierda, -1, 4, 12 y -24, así que la respuesta es 24. El razonamiento requiere que cada valor distinto de cero tenga un valor absoluto de al menos 1, lo cual se cumple para los números enteros.

Algoritmo

Establece best en nums[0] y product en 1.
Recorre de izquierda a derecha: multiplica product por cada elemento y conserva el mayor entre best y product.
Siempre que product se convierta en 0, vuelve a establecerlo en 1 para que la siguiente ejecución empiece desde cero.
Vuelve a establecer product en 1 y haz el mismo recorrido de derecha a izquierda.
Devuelve best.

def maxProduct(nums):
    best = nums[0]
    # Left to right: the product of every prefix of each zero-free run
    product = 1
    for num in nums:
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1  # a zero ends the run, the next one starts fresh
    # Right to left: the product of every suffix of each zero-free run
    product = 1
    for num in reversed(nums):
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1
    return best

Registrar el producto más grande y el más pequeño que terminan aquí

Intuición

Cada subarray que termina en el índice i es solo nums[i], o bien nums[i] multiplicado por un subarray que termina en i-1. Cuando nums[i] es negativo, el mayor de esos productos proviene del menor producto que termina en i-1. Así que mantén ambos: high y low, los productos mayor y menor de un subarray que termina en el índice actual. El nuevo high es el mayor de num, high × num y low × num, y el nuevo low es el menor. Tomar solo num es lo que reinicia la secuencia después de un cero.

En el primer ejemplo, low es -30 cuando llega el -2, y -30 × -2 = 60 se convierte en high, la respuesta.

Algoritmo

Asigna high, low y best a nums[0].
Para cada elemento posterior num, calcula a = high × num y b = low × num.
Asigna a high el mayor y a low el menor de num, a y b.
Asigna a best el mayor de best y high.
Devuelve best.

def maxProduct(nums):
    # high and low: the largest and smallest product of a subarray ending at the current index
    high = low = best = nums[0]
    for num in nums[1:]:
        # Multiply both old values first: a negative num swaps their roles
        a = high * num
        b = low * num
        high = max(num, a, b)
        low = min(num, a, b)
        best = max(best, high)
    return best

Errores comunes y casos límite

Seguir solo el producto más grande. En el primer ejemplo devuelve 4 en lugar de 60, porque descarta el -30 que el -2 convierte en 60.
Calcular el nuevo low a partir del high ya actualizado. Guarda high × num y low × num antes de cambiar cualquiera de los dos.
Iniciar best en 0 o 1. [-3] debe devolver -3, porque el subarreglo no puede estar vacío.
Ejecutar solo la pasada por la izquierda del método de dos pasadas. Con [-2, 3, 4] nunca ve un valor mayor que -2, pero el sufijo [3, 4] da 12.
En JavaScript, TypeScript y Lua, 0 multiplicado por un número negativo es -0, que se muestra con un signo menos. Suma 0 al resultado antes de devolverlo.

Preguntas frecuentes3

¿Cuál es la complejidad temporal del subarreglo de producto máximo?

Registrar el producto más grande y el más pequeño que termina en cada índice requiere un tiempo O(n) y un espacio O(1). El método de prefijos y sufijos en dos pasadas cuesta lo mismo. Multiplicar cada subarreglo desde cada punto de inicio requiere un tiempo O(n²).

¿Por qué necesitas el producto mínimo en la submatriz de producto máximo?

Un número negativo convierte el producto más negativo que termina en el índice anterior en el más grande. Si conservas solo el producto más grande, ese candidato ya no estará cuando lo necesites. En [3, -2, -4], el producto más pequeño antes del -4 es -6, y -6 × -4 = 24 es la respuesta.

¿En qué se diferencia el subarreglo de producto máximo del subarreglo máximo?

En las sumas, un total acumulado negativo solo perjudica, así que basta con un valor por índice. En los productos, un valor acumulado negativo puede convertirse en el mejor después de otro número negativo, y un cero restablece todo. Por eso, la versión para productos conserva el producto más grande y el más pequeño en cada índice.

def maxProduct(nums):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

nums = [2, -5, 3, -2, 0, 4]

Salida Esperada

Maximum Product Subarray

Función

Restricciones

Ejemplos

Pistas

Solución

Multiplica cada subarreglo desde cada inicio

Recorre desde ambos extremos, reiniciando en los ceros

Registrar el producto más grande y el más pequeño que terminan aquí

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares