LeetCode - 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.
Problem statement taken from: https://leetcode.com/problems/maximum-product-subarray.
Example 1:
Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: [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.
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.
Explanation
Brute Force approach
A simple approach is to consider all subarrays and return the maximum product.
A C++ snippet of the approach will look as below:
int result = arr[0];
for (int i = 0; i < n; i++) {
int mul = arr[i];
for (int j = i + 1; j < n; j++) {
result = max(result, mul);
mul *= arr[j];
}
result = max(result, mul);
}
return result;The time-complexity of the above approach is O(N^2), and space complexity is O(1).
Efficient approach
The efficient approach is similar to what we have used in our previous blog post Maximum Subarray. An important thing to notice here is an array can contain both positive and negative numbers as well as zero. The maximum subarray problem used Kadane's algorithm. We tweak this approach and instead use three variables called as max_so_far, max_ending_here and min_ending_here. For each index the maximum number ending at that index will be maximum(arr[i], max_ending_here * arr[i], min_ending_here * arr[i]). Similarly, the minimum number ending here will be the minimum of these 3.
Let's check the algorithm first.
- set max_ending_here, min_ending_here and max_so_far to nums[0]
initialize temp_maximum
- loop for i = 1; i < nums.size(); i++
- temp_maximum = max(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
- min_ending_here = min(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
- max_ending_here = temp_maximum
- max_so_far = max(max_so_far, max_ending_here)
- return max_so_far
Let's check out our solutions in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
int maxProduct(vector<int>& nums) {
int max_ending_here = nums[0];
int min_ending_here = nums[0];
int max_so_far = nums[0];
int temp_maximum;
for(int i = 1; i < nums.size(); i++) {
temp_maximum = max({nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here});
min_ending_here = min({nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here});
max_ending_here = temp_maximum;
max_so_far = max(max_so_far, max_ending_here);
}
return max_so_far;
}
};Golang solution
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func maxProduct(nums []int) int {
max_ending_here, min_ending_here, max_so_far := nums[0], nums[0], nums[0]
var temp_maximum int
for i := 1; i < len(nums); i++ {
temp_maximum = max(nums[i], max(max_ending_here * nums[i], min_ending_here * nums[i]))
min_ending_here = min(nums[i], min(max_ending_here * nums[i], min_ending_here * nums[i]))
max_ending_here = temp_maximum
max_so_far = max(max_so_far, max_ending_here)
}
return max_so_far
}Javascript solution
var maxProduct = function(nums) {
let max_ending_here = nums[0], min_ending_here = nums[0], max_so_far = nums[0];
let temp_maximum
for(let i = 1; i < nums.length; i++) {
temp_maximum = Math.max(nums[i], Math.max(max_ending_here * nums[i], min_ending_here * nums[i]));
min_ending_here = Math.min(nums[i], Math.min(max_ending_here * nums[i], min_ending_here * nums[i]));
max_ending_here = temp_maximum;
max_so_far = Math.max(max_so_far, max_ending_here)
}
return max_so_far;
};Dry Run
Let's dry-run our algorithm to see how the solution works.
Input: nums = [2, 3, -2, 4]
Step 1: max_ending_here, min_ending_here, max_so_far = nums[0], nums[0], nums[0]
max_ending_here = 2
min_ending_here = 2
max_so_far = 2
initialize temp_maximum
Step 2: loop for i = 1; i < nums.size()
i < nums.size()
1 < 4
true
temp_maximum = max(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
= max(nums[1], nums[1] * 2, nums[1] * 2)
= max(3, 3 * 2, 3 * 2)
= max(3, 6, 6)
= 6
min_ending_here = min(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
= min(nums[1], nums[1] * 2, nums[1] * 2)
= min(3, 3 * 2, 3 * 2)
= min(3, 6, 6)
= 3
max_ending_here = temp_maximum
= 6
max_so_far = max(max_so_far, max_ending_here)
= max(2, 6)
= 6
i++
i = 2
Step 3: loop for i < nums.size()
i < nums.size()
2 < 4
true
temp_maximum = max(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
= max(nums[2], nums[2] * 6, nums[2] * 3)
= max(-2, -2 * 6, -2 * 3)
= max(-2, -12, -6)
= -2
min_ending_here = min(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
= min(nums[2], nums[2] * 6, nums[2] * 3)
= min(-2, -2 * 6, -2 * 3)
= min(-2, -12, -6)
= -12
max_ending_here = temp_maximum
= -2
max_so_far = max(max_so_far, max_ending_here)
= max(6, -2)
= 6
i++
i = 3
Step 4: loop for i < nums.size()
i < nums.size()
3 < 4
true
temp_maximum = max(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
= max(nums[3], nums[3] * -2, nums[3] * -12)
= max(4, 4 * -2, 4 * -12)
= max(4, -8, -48)
= 4
min_ending_here = min(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
= min(nums[3], nums[3] * -2, nums[3] * -12)
= min(4, 4 * -2, 4 * -12)
= min(4, -8, -48)
= -48
max_ending_here = temp_maximum
= 4
max_so_far = max(max_so_far, max_ending_here)
= max(6, 4)
= 6
i++
i = 4
Step 5: loop for i < nums.size()
i < nums.size()
4 < 4
false
Step 6: return max_so_far
So we return the answer as 6.