Maximum Product Subarray

Problem Statement

Given an integer array nums, find a subarray that has the largest product within the array and return it.

A subarray is a contiguous non-empty sequence of elements within an array.

You can assume the output will fit into a 32-bit integer.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 1000
  • -10 <= nums[i] <= 10

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

Consider the impact of negative numbers. How do they affect the product?

Hint 2

Think about maintaining both the maximum and minimum product ending at each index.

Hint 3

Kadane’s Algorithm can be adapted to solve this problem.

Solution

Brute Force

def max_product(nums: List[int]) -> int:
res = nums[0]
for i in range(len(nums)):
cur = nums[i]
res = max(res, cur)
for j in range(i + 1, len(nums)):
cur *= nums[j]
res = max(res, cur)
return res

Time complexity: O(n ^ 2)
Space complexity: O(1)