152. Maximum Product Subarray

leetcode medium

#array#bit-manipulation#csharp#leetcode#math#medium

Task

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

Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.

Пример:

Input: nums = [2,3,-2,4]

Output: 6

Explanation: [2,3] has the largest product 6.

C# solution

matched/original

public class Solution {
    public int MaxProduct(int[] nums) {
        if (nums == null || nums.Length == 0) return 0;
        int max = nums[0], min = nums[0], result = nums[0];
        for (int i = 1; i < nums.Length; i++) {
            int temp = max;
            max = Math.Max(Math.Max(max * nums[i], min * nums[i]), nums[i]);
            min = Math.Min(Math.Min(temp * nums[i], min * nums[i]), nums[i]);
            result = Math.Max(result, max);
        }
        return result;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxProduct(vector<int>& nums) {
        if (nums == null || nums.size() == 0) return 0;
        int max = nums[0], min = nums[0], result = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int temp = max;
            max = max(max(max * nums[i], min * nums[i]), nums[i]);
            min = min(min(temp * nums[i], min * nums[i]), nums[i]);
            result = max(result, max);
        }
        return result;
    }
}

Java solution

matched/original

class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;

        int result = nums[0];

        for (int i = 0; i < nums.length; i++) {
            int accu = 1;
            for (int j = i; j < nums.length; j++) {
                accu *= nums[j];
                result = Math.max(result, accu);
            }
        }

        return result;
    }
}

JavaScript solution

matched/original

var maxProduct = function (nums) {
    if (nums.length === 0) return 0;

    let result = nums[0];

    for (let i = 0; i < nums.length; i++) {
        let accu = 1;
        for (let j = i; j < nums.length; j++) {
            accu *= nums[j];
            result = Math.max(result, accu);
        }
    }

    return result;
};

Python solution

matched/original

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

Go solution

matched/original

func maxProduct(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    result := nums[0]

    for i := 0; i < len(nums); i++ {
        accu := 1
        for j := i; j < len(nums); j++ {
            accu *= nums[j]
            if accu > result {
                result = accu
            }
        }
    }

    return result
}

Explanation

Algorithm

1️⃣

Инициализация:

Если массив nums пуст, возвращаем 0, так как нет элементов для обработки.

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

2️⃣

Перебор элементов:

Используем вложенные циклы для обработки всех возможных подмассивов:

Внешний цикл i начинается с начала массива и определяет начальную точку каждого подмассива.

Внутренний цикл j начинается с индекса i и идет до конца массива, последовательно умножая элементы и расширяя рассматриваемый подмассив.

3️⃣

Вычисление произведения и обновление результата:

Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого.

Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result.

😎