Maximum Product Subarray

+10

Перемножьте элементы подмассива nums и верните наибольшее произведение, которое может дать любой подмассив. Подмассив состоит из последовательных элементов без пропусков и никогда не бывает пустым, поэтому даже для массива из отрицательных чисел есть ответ. Допускаются нули и отрицательные значения.

Функция

maxProduct(nums: integer-array) → integer

numsinteger-array: целые числа для умножения, каждое в диапазоне от -10 до 10
Возвращаетinteger: наибольшее произведение непустого подмассива

Ограничения

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
Произведение каждого подмассива помещается в 32-разрядное целое число со знаком.

Примеры

Ввод: nums = [2, -5, 3, -2, 0, 4]
Вывод: 60
Пояснение: Два отрицательных числа взаимно уничтожаются: 2 × -5 × 3 × -2 = 60. 0 делит массив на две части, и 4 с другой стороны не может превзойти 60.

Ввод: nums = [-2, 3, -4, -1]
Вывод: 24
Пояснение: Произведение всего массива равно -24, потому что в нём три отрицательных числа. Если пропустить последний элемент, останутся два из них: -2 × 3 × -4 = 24, что больше 12, получаемых при пропуске первого элемента.

Ввод: nums = [-6, 0, -7]
Вывод: 0
Пояснение: Подмассив, не содержащий 0, состоит из одного отрицательного числа, а произведение элементов подмассива, содержащего 0, равно 0. Лучший выбор — подмассив [0].

Дополнительный вопрос

Как также определить, где начинается и заканчивается наилучший подмассив, по-прежнему за время O(n) и с использованием O(1) памяти?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Умножение на отрицательное число меняет порядок произведений на обратный, поэтому наибольшее произведение на текущем шаге может стать наименьшим на следующем, а умножение на ноль обнуляет все произведения. Вместо одного значения храните для каждого индекса два: наибольшее и наименьшее произведения подмассива, заканчивающегося на этом индексе, — и достаточно одного прохода.

Перемножьте каждый подмассив, начинающийся с каждой позиции

Верно, но не успевает на самых больших тестах

Идея

Зафиксируйте начальный индекс и двигайте конечный вправо, умножая текущий product на каждый новый элемент. Сравнивая его с лучшим результатом после каждого шага, вы переберёте каждый подмассив ровно один раз. Начните с best, равного nums[0], поскольку ответ может быть отрицательным.

Есть около n²/2 пар начального и конечного индексов, по одному умножению на каждую: 2 × 10^8 для 20 000 элементов.

Алгоритм

Установи best равным nums[0].
Для каждого start установи product равным 1.
Перемещай end от start до последнего индекса и умножай product на nums[end].
Если product больше, чем best, сохрани его.
Верни 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

Сканируйте с обоих концов, начиная заново с нулей

Идея

Нули разделяют массив на отрезки без нулей. Внутри такого отрезка каждое значение по модулю не меньше 1, поэтому более длинный подмассив не может иметь меньший модуль произведения; меняется только знак. Если отрицательных чисел чётное количество, оптимален весь отрезок. Если нечётное, нужно убрать одно отрицательное число, и лучше всего отсечь первое отрицательное число вместе со всем, что стоит перед ним, либо последнее отрицательное число вместе со всем, что стоит после него. В любом случае остаётся суффикс или префикс отрезка.

При проходе слева с текущим произведением проверяется каждый префикс, а после 0 произведение сбрасывается до 1. При проходе справа проверяется каждый суффикс. Для [-2, 3, -4, -1] при проходе слева получаются значения -2, -6, 24 и -24, а при проходе справа — -1, 4, 12 и -24, поэтому ответ — 24. Это рассуждение требует, чтобы модуль каждого ненулевого значения был не меньше 1, что выполняется для целых чисел.

Алгоритм

Установи best в значение nums[0], а product — в значение 1.
Пройди слева направо: умножай product на каждый элемент и сохраняй большее из значений best и product.
Когда product становится равным 0, снова установи его в 1, чтобы следующий проход начался заново.
Снова установи product в 1 и выполни такой же проход справа налево.
Верни 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

Отслеживайте наибольшее и наименьшее произведение, заканчивающееся здесь

Идея

Каждый подмассив, заканчивающийся на индексе i, состоит либо только из nums[i], либо из произведения nums[i] на подмассив, заканчивающийся на i-1. Когда nums[i] отрицательное, наибольшее из этих произведений получается из наименьшего произведения, заканчивающегося на i-1. Поэтому сохраняй оба значения: high и low — наибольшее и наименьшее произведения подмассива, заканчивающегося на текущем индексе. Новое значение high — наибольшее из num, high × num и low × num, а новое значение low — наименьшее. Выбор одного только num позволяет начать последовательность заново после нуля.

В первом примере, когда встречается -2, значение low равно -30, а -30 × -2 = 60 становится значением high и ответом.

Алгоритм

Установи high, low и best в nums[0].
Для каждого последующего элемента num вычисли a = high × num и b = low × num.
Установи high равным наибольшему, а low — наименьшему из num, a и b.
Установи best равным большему из best и high.
Верни 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

Ловушки и крайние случаи

Отслеживание только наибольшего произведения. На первом примере это возвращает 4 вместо 60, потому что отбрасывается -30, которое -2 превращает в 60.
Вычисление нового low на основе уже обновлённого high. Сохраните high × num и low × num до изменения любого из них.
Начальное значение best — 0 или 1. Для [-3] нужно вернуть -3, потому что подмассив не может быть пустым.
Выполнение только прохода слева направо в двухпроходном методе. На [-2, 3, 4] он ни разу не видит значение больше -2, но суффикс [3, 4] даёт 12.
В JavaScript, TypeScript и Lua умножение 0 на отрицательное число даёт -0, которое выводится со знаком минус. Перед возвратом результата прибавьте к нему 0.

Частые вопросы3

Какова временная сложность задачи «Подмассив с максимальным произведением»?

Отслеживание наибольшего и наименьшего произведения, заканчивающегося на каждом индексе, занимает время O(n) и пространство O(1). Метод с префиксами и суффиксами в два прохода требует столько же ресурсов. Умножение каждого подмассива, начинающегося с каждой позиции, занимает время O(n²).

Зачем нужен минимум для задачи «Подмассив с максимальным произведением»?

Отрицательное число превращает самое отрицательное произведение, заканчивающееся на предыдущем индексе, в наибольшее. Если хранить только наибольшее произведение, нужный кандидат уже будет потерян. В [3, -2, -4] наименьшее произведение перед -4 равно -6, а -6 × -4 = 24 — это ответ.

Чем задача о подмассиве с максимальным произведением отличается от задачи о подмассиве с максимальной суммой?

Для суммы отрицательная текущая сумма только мешает, поэтому достаточно одного значения для каждого индекса. Для произведения отрицательное текущее значение может стать наибольшим после умножения на ещё одно отрицательное число, а ноль сбрасывает всё. Поэтому в версии для произведения на каждом индексе хранятся наибольшее и наименьшее произведения.

def maxProduct(nums):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

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

Ожидаемый вывод

Maximum Product Subarray

Функция

Ограничения

Примеры

Подсказки

Решение

Перемножьте каждый подмассив, начинающийся с каждой позиции

Сканируйте с обоих концов, начиная заново с нулей

Отслеживайте наибольшее и наименьшее произведение, заканчивающееся здесь

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи