Maximum Product Subarray

+10

Multiplique entre si os elementos de um subarray de nums e retorne o maior produto que qualquer subarray pode gerar. Um subarray contém elementos consecutivos, sem lacunas, e nunca está vazio; portanto, até mesmo um array de valores negativos tem uma resposta. Zeros e valores negativos são permitidos.

Função

maxProduct(nums: integer-array) → integer

numsinteger-array: os números inteiros a serem multiplicados, cada um entre -10 e 10
Retornainteger: o maior produto de um subarray não vazio

Restrições

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
O produto de cada subarray cabe em um inteiro com sinal de 32 bits.

Exemplos

Entrada: nums = [2, -5, 3, -2, 0, 4]
Saída: 60
Explicação: Os dois números negativos se anulam: 2 × -5 × 3 × -2 = 60. O 0 divide o array em dois, e o 4 do outro lado não consegue superar 60.

Entrada: nums = [-2, 3, -4, -1]
Saída: 24
Explicação: O array inteiro resulta em -24 porque contém três números negativos. Ao deixar de fora o último elemento, restam dois deles: -2 × 3 × -4 = 24, que é maior que 12, o resultado de deixar de fora o primeiro elemento.

Entrada: nums = [-6, 0, -7]
Saída: 0
Explicação: Um subarray que não inclui o 0 é um único número negativo, e um subarray que inclui o 0 tem produto igual a 0. A melhor escolha é o subarray [0].

Para ir além

Como você também informaria onde o melhor subarray começa e termina, ainda em tempo O(n) e espaço O(1)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Multiplicar por um número negativo inverte a ordem dos produtos, então o menor produto até o momento pode se tornar o maior no passo seguinte, e um zero zera todos os produtos. Armazene dois valores em cada índice em vez de um: o maior e o menor produto de um subarray que termina ali. Uma única passagem é suficiente.

Multiplique cada subarray a partir de cada início

Correta, mas não termina nos maiores testes

Intuição

Fixe um índice inicial e mova o final para a direita, multiplicando um product acumulado por cada novo elemento. Compará-lo com o melhor resultado após cada etapa abrange cada subarray uma vez. Inicie best com nums[0], pois a resposta pode ser negativa.

Há cerca de n²/2 pares de início e fim, com uma multiplicação cada: 2 × 10^8 para 20.000 elementos.

Algoritmo

Defina best como nums[0].
Para cada start, defina product como 1.
Mova end de start até o último índice e multiplique product por nums[end].
Se product for maior que best, armazene-o.
Retorne 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

Examine de ambas as extremidades, reiniciando nos zeros

Intuição

Os zeros dividem o array em trechos sem zeros. Dentro de um trecho, todo valor tem magnitude de pelo menos 1, então um subarray mais longo nunca tem um produto absoluto menor; apenas o sinal muda. Se houver um número par de negativos, o trecho inteiro é a melhor opção. Se houver um número ímpar, é preciso descartar um negativo, e o melhor corte descarta o primeiro negativo e tudo o que vem antes dele, ou o último negativo e tudo o que vem depois dele. Em ambos os casos, você mantém um sufixo ou um prefixo do trecho.

Uma passagem da esquerda para a direita, mantendo um produto acumulado, verifica cada prefixo e o redefine para 1 após um 0. Uma passagem da direita para a esquerda verifica cada sufixo. Em [-2, 3, -4, -1], a passagem da esquerda vê -2, -6, 24 e -24; a da direita vê -1, 4, 12 e -24, então a resposta é 24. O argumento exige que todo valor diferente de zero tenha magnitude de pelo menos 1, o que vale para números inteiros.

Algoritmo

Defina best como nums[0] e product como 1.
Percorra da esquerda para a direita: multiplique product por cada elemento e mantenha o maior entre best e product.
Sempre que product se tornar 0, defina-o novamente como 1 para que o próximo trecho comece do zero.
Defina product como 1 novamente e faça o mesmo percurso da direita para a esquerda.
Retorne 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

Rastreie o maior e o menor produto que termina aqui

Intuição

Cada subarray que termina no índice i é apenas nums[i] ou nums[i] multiplicado por um subarray que termina em i-1. Quando nums[i] é negativo, o maior desses produtos vem do menor produto que termina em i-1. Então, mantenha ambos: high e low, os maiores e menores produtos de um subarray que termina no índice atual. O novo high é o maior entre num, high × num e low × num, e o novo low é o menor. Considerar apenas num é o que reinicia a sequência após um zero.

No primeiro exemplo, low é -30 quando o -2 chega, e -30 × -2 = 60 se torna high, a resposta.

Algoritmo

Defina high, low e best como nums[0].
Para cada elemento posterior num, calcule a = high × num e b = low × num.
Defina high como o maior e low como o menor entre num, a e b.
Defina best como o maior entre best e high.
Retorne 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

Armadilhas e casos extremos

Acompanhar apenas o maior produto. No primeiro exemplo, isso retorna 4 em vez de 60, porque descarta o -30 que o -2 transforma em 60.
Calcular o novo low usando o high já atualizado. Salve high × num e low × num antes de alterar qualquer um deles.
Inicializar best com 0 ou 1. [-3] deve retornar -3, porque o subarray não pode ser vazio.
Executar apenas a passagem da esquerda do método de duas passagens. Em [-2, 3, 4], ele nunca encontra um valor maior que -2, mas o sufixo [3, 4] resulta em 12.
Em JavaScript, TypeScript e Lua, 0 vezes um número negativo é -0, que é exibido com um sinal de menos. Adicione 0 ao resultado antes de retorná-lo.

Perguntas frequentes3

Qual é a complexidade de tempo do subarray de produto máximo?

Acompanhar o maior e o menor produto que termina em cada índice leva O(n) de tempo e O(1) de espaço. O método de prefixo e sufixo em duas passagens tem o mesmo custo. Multiplicar todos os subarrays a partir de cada início leva O(n²) de tempo.

Por que você precisa do produto mínimo em Subarray de Produto Máximo?

Um número negativo transforma o produto mais negativo que termina no índice anterior no maior. Se você mantiver apenas o maior produto, esse candidato não estará mais disponível quando precisar dele. Em [3, -2, -4], o menor produto antes do -4 é -6, e -6 × -4 = 24 é a resposta.

Qual é a diferença entre o Subarray de Produto Máximo e o Subarray Máximo?

Para somas, um total acumulado negativo só atrapalha, então um valor por índice é suficiente. Para produtos, um valor acumulado negativo pode se tornar o melhor após outro número negativo, e um zero reinicia tudo. Por isso, a versão para produtos mantém o maior e o menor produto em cada índice.

def maxProduct(nums):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada

Maximum Product Subarray

Função

Restrições

Exemplos

Dicas

Solução

Multiplique cada subarray a partir de cada início

Examine de ambas as extremidades, reiniciando nos zeros

Rastreie o maior e o menor produto que termina aqui

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos