How to Solve the Maximum Product Subarray Problem on Leetcode

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.