Given an integer array, find the contiguous subarray within the array (containing at least one number) that has the largest product. Return the maximum product.

Function Signature:

from typing import List

def max_product(nums: List[int]) -> int:
    """
    Find the maximum product of a contiguous subarray.

    Parameters:
    - nums: List of integers.

    Returns:
    - int: Maximum product of a contiguous subarray.
    """
    # Your code here

Example:

# Input: nums = [2, 3, -2, 4]
# Output: 6
# Explanation: The contiguous subarray [2, 3] has the largest product (2 * 3 = 6).

# Input: nums = [-2, 0, -1]
# Output: 0
# Explanation: The contiguous subarray [-2, 0] has the largest product (0), and the subarray [-1] also has a product of -1.

# Input: nums = [1,2,-2, 100, -2]
# Output: 800

Instructions:

  • Write the max_product function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊