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
Recommended Time and Space Complexity
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)