How to Solve the Maximum Product Subarray Problem on Leetcode

3 min read
Table of contents

The problem: return maximum product of elements from a subarray in the given array,
Given:
1 <= nums.length <= 2 * 10<sup>4</sup>
-10 <= nums[i] <= 10
The product of any subarray of
nums
is guaranteed to fit in a 32-bit integer.
Solution:
Nested Loops
Kadane’s Algorithm
Nested Loops
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
int prod = 0; // we are not multiplying this to anything -just updating the value, so we
// can assign the value as 0
for (int i = 0; i < n; ++i) {
int subProd = 1; // we have to change the subProd back to 1 for each main iteration.
for (int j = i; j < n; ++j) {
subProd *= nums[j];
prod = prod < subProd ? subProd : prod;
}
}
return prod;
}
};
Time Complexity is O(n²)
.
Hence, this is not the solution.
Kadane’s Algorithm - Modified
→ Something I did
class Solution {
public:
int maxProduct(std::vector<int>& nums) {
int max = nums[0];
int min = nums[0];
int prod = nums[0];
// start from the second element, cuz we have alredy initialized the var thats going to be return with first element.
for (int i = 1; i < nums.size(); ++i) {
int num = nums[i];
int subMax = max;
int var1 = subMax * num; //gets the product thats max in this iteration
int var2 = min * num; // gets the product of thats min all over
max = (num > var1) ? num : var1;
max = (max > var2) ? max : var2; // checks for the maximum product from the three
min = (num < var1) ? num : var1;
min = (min < var2) ? min : var2; // checks for the minimum product from the three
prod = (prod > max) ? prod : max; // does a final check and update on product.
}
return prod;
}
};
→ In Solution
class Solution {
public:
int maxProduct(vector<int>& nums) {
int max = 0;
int prod = 1;
for(int i = 0 ; i < nums.size(); i++) // left to right iteration
{
prod *= nums[i];
max = prod > max ? prod : max;
if ( prod == 0 ) {
prod = 1;
}
}
prod = 1; // note: max is not updated in the right to left iteration. hence the value is passed
// so that the overall maximum cold be calculated.
for(int i = nums.size()-1; i>=0; i--)
{
prod *= nums[i];
max = prod > max ? prod : max;
if(prod == 0)
prod = 1;
}
return max;
}
};
Time Complexity is O(n)
.
This is the Solution.
Kadane’s Algorithm is so simple yet looks so cool and smart. I am having fun trying out different ways to implement the core concept from this elegant technique, hope you do too.
Best of luck.
0
Subscribe to my newsletter
Read articles from Java directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
