Эта статья является частью серии статей Натана Томаса, разработчика программного обеспечения полного стека, работающего в Сан-Франциско, Калифорния. Среди других его недавних статей — Создание собственного биткойн-узла и Лучшее время для покупки и продажи акций.
Введение
Если вы ищете краткое руководство по оптимальному решению задачи LeetCode Максимальный подмассив продукта, вы попали по адресу.
Этот вопрос входит в Список вызовов кода для слепых 75 LeetCode — группу вопросов, составленную техническим руководителем Facebook, которая рекламируется как отличный способ подготовиться к собеседованию.
Не корите себя слишком сильно, если вы здесь, потому что вам пришлось нелегко. У всех время от времени возникают проблемы с кодированием.
С учетом сказанного, давайте приступим к делу, чтобы вы могли получить свое решение.
Первоначальная настройка 🏗
Прежде чем писать хоть одну строчку кода, мы должны попытаться понять все правила задачи (см.: Техники решения проблем Поля):
- Нам будет дан список целых чисел с именем
nums, которые будут равны< 1и<= 2 * 10^4. - Список не будет пустым
- Мы должны найти наибольший продукт подмассива внутри списка
nums
Это хорошо на данный момент. Мы должны быть в состоянии начать.
Я буду использовать Python для ответа на этот вопрос, поскольку он немного похож на универсальный язык — предпочитаете ли вы JavaScript, Java, Golang, C или что-то еще, каждый может «отчасти» читать Python.
Я также не буду говорить о «менее оптимальных» решениях. Вы пришли сюда за ответом, верно? Я собираюсь убедиться, что вы получите хороший.
Давай сделаем это.
Как на Земле?? 🌍
Эта проблема может быть немного глупой, если вы не знаете несколько ключевых вещей, которые нужно искать. Возможно, вы пытались решить эту проблему с помощью вложенных for циклов или другого подобного подхода. Я знаю, что я сделал в первый раз, когда я увидел это.
Оказывается, ключом к этой проблеме является то, что мы должны использовать супермодифицированный алгоритм Кадане. Этот алгоритм является ответом на проблему Максимальный подмассив суммы и вращается вокруг добавления каждого числа одно за другим, отслеживания наибольшей общей суммы, наблюдаемой до сих пор, и сброса текущего значения суммы до 0, если оно падает ниже 0. Подробнее об этом алгоритме можно прочитать здесь.
Проблема в том, что алгоритм Кадане здесь не работает прямо из коробки. Что произойдет, если мы умножим на 0? Что произойдет, если у нас есть отрицательные числа?
Мы доберемся до всего этого. Не волнуйтесь, к концу вы станете профессионалом.
Решение этой проблемы заключается в отслеживании как текущего наибольшего, так и текущего наименьшего числа. Это позволит нам умножать на отрицательные числа и по-прежнему иметь возможность отслеживать самые большие товары.
Перейдем к проблеме и коду. 👨🏻💻
Подготовительная работа 🔥
Первое, что мы сделаем, — это создадим наши исходные переменные, которые мы будем использовать для отслеживания и хранения наших данных на протяжении всего цикла, который мы также собираемся построить.
Во-первых, нам нужно добавить переменную с именем maximum_product. Это будет то, что мы в конечном итоге вернем из нашей функции в качестве ответа. Нам нужно инициализировать его первым элементом в массиве nums.
Следующее, что нам нужно, это две переменные, в которых мы можем отслеживать текущий самый большой продукт и текущий самый маленький продукт. Нам нужно инициализировать их обоих как 1 вместо 0, так как мы будем умножать их, когда начинаем наш цикл. Использование 0 приведет к тому, что все наше решение будет 0, когда мы закончим умножение на него.
Вот как это выглядит внутри начала функции, которую мы будем использовать для решения этой задачи:
Обратите внимание, что этот шаблон использования 1 в качестве основы в задачах кода, где вы делаете много умножения, очень распространен.
Стоит отложить это на черный день для другого испытания кода. 👍🏻
Построение нашей петли 🌀
Хорошо, мы готовы начать работу над нашим циклом for!
Первое, что нам нужно сделать, это написать цикл, который перебирает весь наш список nums. Это будет выглядеть так:
Помните ранее, когда я упоминал, что мы будем отслеживать самые большие и самые маленькие текущие продукты для каждого значения? Теперь у нас есть переменные вне цикла, и нам нужно умножить их внутри цикла на текущее num.
Однако у нас есть проблема. Вы представляете, с чем мы сейчас столкнемся, если наш список nums будет выглядеть примерно так?
nums = [4, -10, -5, -3, 5, 8, 10, -2, 0, 5, 9]
Что произойдет, если мы умножим несколько отрицательных чисел вместе?
Означает ли это, что наши значения largest_current_product и smallest_current_product могут поменяться местами, если мы несколько раз умножим на отрицательное?
Оно делает!
Способ компенсации — использование вспомогательных функций max() и min(), которые Python предоставляет нам из коробки. Ваш любимый язык, вероятно, имеет что-то подобное.
Что мы можем сделать, так это сохранить значение largest_current_product во временной переменной (подробнее о том, почему это делается чуть позже), а затем установить largest_current_product равным максимальному значению либо num, умноженного на num, либо smallest_current_product, умноженного на num.
Включение num в это число гарантирует, что, если мы ранее умножали на 0 (в списке что-то вроде [3, 9, 0, 2, 5]), мы сбрасывали наше значение на 2 на следующей итерации цикла, поскольку оно будет больше, чем 0.
Здесь ключевое значение имеет smallest_current_product, умноженное на num. Это то, что позволяет нам учитывать многократное умножение на отрицательные числа.
Как вы можете видеть в приведенном выше коде, мы в конечном итоге устанавливаем smallest_current_product с минимальным значением. Мы также используем здесь temp_largest_current_product для нашего умножения, потому что мы только что изменили largest_current_product в строке выше и больше не можем полагаться на него для старого значения.
Наконец, нам нужно также добавить строку, назначающую новый максимум для maximum_product, которая выбирает между его существующим значением, num или largest_current_product:
Последнее, что нам нужно, это включить оператор возврата, в котором мы возвращаем maximum_product из нашей функции.
Когда мы собираем все это вместе, это окончательный ответ, который мы получаем:
Бум.
Это решение работает со сложностью времени O(n) (поскольку мы используем только цикл for, который не является вложенным) и сложностью пространства O(1) (поскольку наши переменные в памяти постоянны независимо от того, насколько велик наш список nums).
Заключение
Поздравляю с завершением задачи! Я знаю, что это могло быть более жестким. 😅
Следите за остальными статьями Слепые 75 проблем с программированием от меня. Я собираюсь решать их и публиковать по ходу дела.
Кроме того, не стесняйтесь обращаться ко мне по любой из ссылок ниже, если вы хотите поговорить о программировании, крутых технологиях или о чем-то еще (мне очень нравятся рекомендации книг).
Спасибо за прочтение. 🔥
Натан
