Last updated on February 28th, 2025 at 02:01 pm

Here, we see a Maximum Product Subarray LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Depth-First Search, Tree

Companies

Microsoft

Level of Question

Medium

Maximum Product Subarray LeetCode Solution

1. Problem Statement

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:
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.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Dynamic Programming (DP). Specifically, it is a “Kadane’s Algorithm for Maximum Product Subarray”. This pattern involves maintaining intermediate results (like maximum and minimum products) to solve the problem efficiently.

3. Code Implementation in Different Languages

3.1 Maximum Product Subarray C++

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxi = INT_MIN;
        int prod=1;
        for(int i=0;i<nums.size();i++)
        {
          prod*=nums[i];
          maxi=max(prod,maxi);
          if(prod==0)
           prod=1;
        }
        prod=1;
        for(int i=nums.size()-1;i>=0;i--)
        {
          prod*=nums[i];
          maxi=max(prod,maxi);
          if(prod==0)
           prod=1;
        }
        return maxi;
    }
};

3.2 Maximum Product Subarray Java

class Solution {
    public int maxProduct(int[] nums) { 
        int max = nums[0], min = nums[0], ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int temp = max;
            max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
            min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);   
            if (max > ans) {
                ans = max;
            }
        }     
        return ans;
    }
}

3.3 Maximum Product Subarray JavaScript

var maxProduct = function(nums) {
    let prevMax = nums[0];
    let prevMin = nums[0];
    let result = nums[0];
    for (let i=1;i<nums.length;i++) {
        curMax = Math.max(nums[i] * prevMax, nums[i], nums[i] * prevMin);
        curMin = Math.min(nums[i] * prevMin, nums[i], nums[i] * prevMax);
        prevMax = curMax
        prevMin = curMin
        result = Math.max(curMax, result);
    }
    return result;
}

3.4 Maximum Product Subarray Python

class Solution(object):
    def maxProduct(self, nums):
        global_max = prev_max = prev_min = nums[0]
        for num in nums[1:]:
            curr_min = min(prev_max*num, prev_min*num, num)
            curr_max = max(prev_max*num, prev_min*num, num)
            global_max= max(global_max, curr_max)
            prev_max = curr_max
            prev_min = curr_min
        return global_max

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(1)
JavaScript	O(n)	O(1)
Python	O(n)	O(1)

• All implementations solve the same problem using variations of dynamic programming.
• The C++ code uses a two-pass approach, while the others use a single-pass approach.
• The time complexity is O(n) for all, and the space complexity is O(1) since no additional data structures are used.