Maximum Product Subarray medium

Problem Statement

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

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.

Steps to Solve

The key idea is to maintain two variables at each position: max_so_far and min_so_far. max_so_far stores the maximum product ending at the current position, and min_so_far stores the minimum product ending at the current position. This is because a negative number multiplied by a negative number becomes positive, so the minimum product could become the maximum product in the next iteration.

1. Initialization: Initialize max_so_far and min_so_far to the first element of the array. Also initialize result to the first element (this will hold the overall maximum product).

2. Iteration: Iterate through the array from the second element.

3. Update max_so_far and min_so_far: For each element, calculate three potential values:

   • The product of the current element and max_so_far
   • The product of the current element and min_so_far
   • The current element itself

   Update max_so_far and min_so_far to the maximum and minimum of these three values, respectively.

4. Update result: Update result to the maximum of result and max_so_far.

5. Return result: After iterating through the entire array, return result.

Explanation

The algorithm efficiently handles both positive and negative numbers. By tracking both the maximum and minimum products so far, it correctly accounts for scenarios where multiplying by a negative number might lead to a larger product than previously seen. The use of max and min ensures we always select the largest possible product at each step, ultimately leading to the global maximum product.

Code (Python)

def maxProduct(nums):
    """
    Finds the maximum product of a contiguous subarray.

    Args:
      nums: A list of integers.

    Returns:
      The maximum product of a contiguous subarray.
    """
    max_so_far = nums[0]
    min_so_far = nums[0]
    result = max_so_far

    for i in range(1, len(nums)):
        temp_max = max(nums[i], max_so_far * nums[i], min_so_far * nums[i])
        min_so_far = min(nums[i], max_so_far * nums[i], min_so_far * nums[i])
        max_so_far = temp_max
        result = max(max_so_far, result)

    return result

Complexity Analysis

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). We use only a few constant extra variables.