Maximum Product Subarray
Problem Description
Given an integer array nums, find a subarray 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.
Example 1:
Explanation: [2,3] has the largest product 6.
Example 2:
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
- 1 <= nums.length <= 2 * 104
- -10 <= nums[i] <= 10
- The product of any subarray of
numsis guaranteed to fit in a 32-bit integer.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The brute force approach is to generate all possible subarrays of the given array and calculate their products. Among all these products, we find the maximum product.
Steps:
- Use a nested loop to consider every subarray from
itoj. - For each subarray, compute the product.
- Track the maximum product encountered.
Code:
- Time Complexity: O(n^2) — Two nested loops to evaluate every possible subarray.
- Space Complexity: O(1) — Constant space used.
2. Dynamic Programming (Kadane's Algorithm)
Intuition:
The product of elements in subarrays can be disrupted by negative numbers and zeros. A negative number turns a positive product into negative and vice versa, while zero resets it. Thus, we need to track both the maximum and minimum product subarrays because a negative product might become the largest if multiplied by another negative number.
Instead of recalculating products for every possible subarray, we maintain two potential products:
maxProductSoFar: Maximum product subarray ending at the current position.minProductSoFar: Minimum product subarray ending at the current position (to handle the case of two negative numbers resulting in a positive product).
Steps:
- Iterate through the array, maintaining both
maxProductSoFarandminProductSoFar. - If a negative number is encountered, swap
maxProductSoFarandminProductSoFar. - Update the
maxProductSoFarandminProductSoFarat each step. - Track the global maximum product.
Code:
- Time Complexity: O(n) — Iterate over the array once.
- Space Complexity: O(1) — Only a constant amount of extra space is used to store intermediate results.