Maximum Product Subarray
Problem Statement
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer. A subarray is a contiguous subsequence of the array.
Constraints:
- 1 <= nums.length <= 2 * 10^4
- -10 <= nums[i] <= 10
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer
Input Format:
- An integer array nums
Output Format:
- Return the maximum product of a contiguous subarray within nums
Examples:
Example 1:
Input:
nums = [2,3,-2,4]
Output:
6
Explanation:
The subarray [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.
Example 3:
Input:
nums = [-2,3,-4]
Output:
24
Explanation:
The subarray [-2,3,-4] has the largest product 24.
Solutions
Dynamic Programming Approach
At each position, we keep track of both the maximum and minimum products ending at that position. This is because a negative number can produce a larger product when multiplied by another negative number.
Brute Force Approach
Consider all possible subarrays and calculate their products. Keep track of the maximum product found.
Two-Pass Scanning Approach
Scan the array from left to right and right to left, computing running products. This handles cases where an even number of negative numbers might create a large positive product.
Algorithm Walkthrough
Example input: nums = [2,3,-2,4]
Step-by-step execution:
- Initialize maxSoFar=2, minSoFar=2, result=2
- i=1: curr=3, tempMax=max(3, max(2*3, 2*3))=6, minSoFar=min(3, min(2*3, 2*3))=3, maxSoFar=6, result=6
- i=2: curr=-2, tempMax=max(-2, max(6*-2, 3*-2))=-2, minSoFar=min(-2, min(6*-2, 3*-2))=-12, maxSoFar=-2, result=6
- i=3: curr=4, tempMax=max(4, max(-2*4, -12*4))=4, minSoFar=min(4, min(-2*4, -12*4))=-48, maxSoFar=4, result=6
- Return result=6
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the dynamic programming approach and how both maximum and minimum products are tracked at each position.
Key visualization elements:
- current element
- max product so far
- min product so far
- result
Similar Questions
Maximum Subarray
EasyGiven an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Product of Array Except Self
MediumGiven an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.
Implementation Notes
This problem is a variation of the Maximum Subarray problem but requires handling negative numbers, which can produce larger products when multiplied together.