Сложность: Medium
Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение.
Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.
Пример:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
👨💻 Алгоритм:
1️⃣Инициализация: Если массив nums пуст, возвращаем 0, так как нет элементов для обработки. Инициализируем переменную result первым элементом массива, чтобы иметь начальную точку сравнения для нахождения максимального произведения.
2️⃣Перебор элементов: Используем вложенные циклы для обработки всех возможных подмассивов: Внешний цикл i начинается с начала массива и определяет начальную точку каждого подмассива. Внутренний цикл j начинается с индекса i и идет до конца массива, последовательно умножая элементы и расширяя рассматриваемый подмассив.
3️⃣Вычисление произведения и обновление результата: Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого. Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result.
😎 Решение:
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
result = nums[0]
for i in range(len(nums)):
accu = 1
for j in range(i, len(nums)):
accu *= nums[j]
result = max(result, accu)
return result
Ставь 👍 и забирай 📚 Базу знаний