152. Maximum Product Subarray Leetcode Solution
Maximum Product Subarray Leetcode Problem :
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.
Maximum Product Subarray Leetcode Solution :
Constraints :
- 1 <= nums.length <= 2 * 104
- -10 <= nums[i] <= 10
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Example 1:
- Input: nums = [-2,0,-1]
- Output: 0
Intuition :
This problem is really similar to Maximum Subarray except instead of a sum it’s a product, so naturally, a DP solution also comes to mind.
Approach :
In this question, we need to keep track of two subarrays: the subarray with the maximum product so far and the subarray with the minimum product so far. Why do we need to keep track of the minimum product? To handle the negative case. Let’s revisit that negative subarray again:
nums = [2, -2, 2, -2]
When we are 3 indices in [2, -2, 2], the running product of all 3 elements is negative. The maximum product so far is 2 (just a singular element in the subarray), but the minimum subarray is [2 -2 2] with a product of -8. Now, when we calculate the solution for all 4 indices, we consider both the max product and the min product to get 16.
There are 3 DP cases to consider
- Restart new subarray
- Set the running product to be just the current element
- This handles the case with 0s
- Add current element to the current subarray with the minimum product
- Set running product to be minimum_product * value
- Add current element to the current subarray with the maximum product
- Set running product to be maximum_product * value
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int maxProduct(vector< int>& nums) {
int minProd = nums[0], maxProd = nums[0], ans = nums[0];
for (auto i = 1; i < nums.size(); i++) {
int value = nums[i];
int testMaxProd = maxProd * value;
int testMinProd = minProd * value;
maxProd = max({testMaxProd, testMinProd, value});
minProd = min({testMaxProd, testMinProd, value});
ans = max(ans, maxProd);
}
return ans;
}
};
class Solution {
public int maxProduct(int[] nums) {
int minProd = nums[0], maxProd = nums[0];
int ans = nums[0];
int testMaxProd, testMinProd;
for (int i = 1; i < nums.length; i++) {
testMaxProd = maxProd * nums[i];
testMinProd = minProd * nums[i];
maxProd = Math.max(Math.max(testMaxProd, testMinProd), nums[i]);
minProd = Math.min(Math.min(testMaxProd, testMinProd), nums[i]);
ans = Math.max(ans, maxProd);
}
return ans;
}
}
class Solution:
def maxProduct(self, nums: List[int]) -> int:
min_prod = max_prod = ans = nums[0]
for value in nums[1:]:
max_temp = max_prod * value
min_temp = min_prod * value
min_prod = min(max_temp, min_temp, value)
max_prod = max(max_temp, min_temp, value)
ans = max(ans, max_prod)
return ans
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment