LeetCode-in-All

152. Maximum Product Subarray

Medium

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:

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

Output: 6

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

Example 2:

Input: nums = [-2,0,-1]

Output: 0

Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution

-spec max_product(Nums :: [integer()]) -> integer().
max_product(Nums) ->
    max_product(Nums, 1, 1, -(1 bsl 31)).

-spec max_product(Nums :: [integer()], integer(), integer(), integer()) -> integer().
max_product([], _, _, MaxProduct) ->
    MaxProduct;
max_product([H|T], MaxCurrent, MinCurrent, MaxProduct) ->
    % The new maximum and minimum products are derived by comparing
    % the current number, its product with the maximum so far, and its product with the minimum so far
    NewMaxCurrent = max(max(H, H * MaxCurrent), H * MinCurrent),
    NewMinCurrent = min(min(H, H * MaxCurrent), H * MinCurrent),
    NewMaxProduct = max(MaxProduct, NewMaxCurrent),
    max_product(T, NewMaxCurrent, NewMinCurrent, NewMaxProduct).

This site is open source. Improve this page.