[Решение] Leetcode #152. Maximum Product Subarray

Условие задачи: https://t.iss.one/leetcode_furrycat/39

Задачка с поиском подмассива с максимальным произведением похожа на задачу с поиском подмассива с максимальной суммой, поэтому и решать мы ее будем похожим образом: с использованием алгоритма Кадане.

Для задачи с наибольшей суммой его суть заключалась в том, что мы проходили по массиву слева направо и вычисляем наибольшую возможную сумму для ТЕКУЩЕГО элемента (от начала массива до текущего элемента). А затем просто брали максимальное из полученных значений.

Но с произведением все немного по-другому. Здесь у нас есть нули, которые любой подмассив сведут к нулю, а также отрицательные числа, которые по одиночке радикальном уменьшают общее произведение, но парами очень даже увеличивают. То есть здесь мы не можем сказать, что максимально возможное произведение для 2-го элемента - это именно то, что нам нужно, чтобы получить максимальное произведение для 3-го элемента.

Пример:

const nums = [-2, 3, -4]

для n=1: maxTillNow = -2
для n=2: maxTillNow = Math.max(3, -6) = 3
для n=3: maxTillNow = Math.max(3, -12) = 3

Очевидно, что этот алгоритм неправильный, и чтобы получить максимум для третьего элемента, нам следует взять -6 на предыдущем шаге.

В целом очевидно, что для массива состоящего только из положительных чисел максимальным подмассивом является сам этот массив (все элементы, умноженные друг на друга). Поэтому мы будем вычислять произведение непрерывно. То есть для каждого элемента мы найдем произведение ВСЕХ элементов до него, включая сам активный элемент.

Если в какой-то момент накапливаемое произведение стало равно 0, значит, нам попался элемент 0. В этом случае просто сбросим его до исходной единицы и продолжим считать уже после этого элемента.

А чтобы избежать разнообразных эксцессов с отрицательными числами, пройдем по массиву два раза - слева направо и справа налево:

1 - Если в массиве четное количество отрицательных чисел, то очевидно, что при обратном проходе ничего не изменится.
2 - Если же в массиве нечетное количество отрицательных чисел, то с помощью второго прохода мы сможем получить все комбинации подмассивов (слева и справа от отрицательного числа) и выбрать максимальную.

function maxProduct(nums) {
    let currentProduction = 1;
    let maxTillNow = -Infinity;

    for (let i = 0; i < nums.length; i++) {  
        const el = nums[i];
        currentProduction *= el;
        maxTillNow = Math.max(maxTillNow, currentProduction);
        if (currentProduction === 0) {
            currentProduction = 1;
        }
    }

    currentProduction = 1;

    for (let i = nums.length - 1; i >= 0; i--) {
        const el = nums[i];
        currentProduction *= el;
        maxTillNow = Math.max(maxTillNow, currentProduction);
        if (currentProduction === 0) {
            currentProduction = 1;
        }    
    }

    return maxTillNow;
}

Временная сложность: O(N) - мы делаем два прохода по массиву, но коэффициент отбрасывается

#medium #arrays #dp #prefixsum

@leetcode_furrycat

Blind 75. Arrays

Небольшое ретро по задачкам из раздела Массивы:

1 - Two sum (easy)
11 - Container With Most Water (medium)
15 - 3Sum (medium)
33 - Search in Rotated Sorted Array (medium)
53 - Maximum Subarray (medium)
121 - Best Time to Buy and Sell Stock (easy)
152 - Maximum Product Subarray (medium)
153 - Find Minimum in Rotated Sorted Array (medium)
217 - Contains Duplicate (ease)
238 - Product of Array Except Self (medium)

Какие подходы к решению использовались:

👉 Два указателя (#twopointers)

Используется, когда "второй" элемент всегда идет после "текущего". Часто используется для отбора последовательно идущих элементов, которые в комбинации соответствуют определенному условию.

- два/три элемента, составляющие определенную сумму (Two sum, 3Sum)
- две линии, составляющие прямоугольник наибольшей площади (Container With Most Water)
- две даты, между которыми акция росла больше всего (Best Time to Buy and Sell Stock)

👉 Хеш-таблица (#hashtable)

Используется для быстрого доступа к элементам массива (элементы массива становятся ключами хеш-таблицы).

- Быстро найти второе слагаемое для известной суммы и первого слагаемого (Two sum)
- Найти дубликаты ( Contains Duplicate)

👉 Разделяй и властвуй (#divideandconquer)

Используется с отсортированными массивами, когда есть возможность определить, в какой части массива находится нужное значение. Часто используется для поиска (бинарный поиск) элемента (Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array). Но может использоваться и в более сложном виде, например, для поиска подмассива с максимальной суммой (Maximum Subarray).

👉 Рекурсия (#recursion)

Используется, когда мы можем по какому-либо принципу сократить исходные данные (например, уменьшить массив) и выполнить для уменьшенных данных те же самые действия. Требуется обработка крайнего случая, когда дальнейшее сокращение данных невозможно (пустой массив). Возможны проблемы с переполнением стека.

Например, мы использовали рекурсию для поиска подмассива с максимальной суммой (Maximum Subarray).

👉 Динамическое программирование (#dp)

У динамического программирования есть несколько разновидностей: мемоизация и табуляция. Сюда же можно включить вычисление префиксных сумм (#prefixsum). Подвидом ДП является алгоритм Кадане.
Суть метода в том, что мы используем результаты предыдущих вычислений.
Динамическое программирование часто используется в задачах с массивами для нахождения подмассива с заданными свойствами, например, с максимальной суммой (Maximum Subarray, Maximum Product Subarray)
Также с его помощью (префиксные суммы) мы вычисляли произведение всех элементов массива кроме текущего (Product of Array Except Self).

👉 Set

При работе с массивами может быть полезна структура данных Set, которая позволяет быстро удалить дубликаты из массива (Contains Duplicate), а также обеспечивает быстрый доступ к элементам массива по их значению.

#arrays #ретро

@leetcode_furrycat