LeetCode Solutions Blog

Maximum Product Subarray

Number: 152

Difficulty: Medium

Paid? No

Problem Description

Given an integer array nums, find a contiguous subarray within the array (containing at least one number) which has the largest product, and return that product.

Key Insights

Maintain both the maximum and minimum product at the current index because a negative number can swap the max and min.
A subarray must be contiguous.
Use dynamic programming to update both the maximum product and the minimum product ending at each index.
Resetting the product in case of a zero is crucial since the product becomes 0.

Space and Time Complexity

Time Complexity: O(n) – The solution iterates through the array once. Space Complexity: O(1) – Constant space is used for tracking products.

Solution

The solution uses an iterative dynamic programming approach. At each index, compute the maximum product (maxEndingHere) and minimum product (minEndingHere) ending at that index. If the current element is negative, swap these two values, because multiplying a negative with a minimum product (possibly negative) might yield a larger product. After processing each element, update the global maximum. This method handles edge cases like zeros and negatives efficiently with constant additional space.

Code Solutions

def maxProduct(nums):
    # If the input array is empty, return 0 (though problem guarantees at least one element)
    if not nums:
        return 0
    # Initialize maximum, minimum product ending here and the result.
    max_ending_here = nums[0]
    min_ending_here = nums[0]
    global_max = nums[0]
    
    # Iterate over the array starting from the second element.
    for num in nums[1:]:
        # If the current number is negative, swap max and min.
        if num < 0:
            max_ending_here, min_ending_here = min_ending_here, max_ending_here
        # Update the max product at the current index.
        max_ending_here = max(num, max_ending_here * num)
        # Update the min product at the current index.
        min_ending_here = min(num, min_ending_here * num)
        # Update the global maximum product.
        global_max = max(global_max, max_ending_here)
    
    return global_max

# Example usage:
# print(maxProduct([2,3,-2,4]))  # Output: 6