Maximum Product Subarray in an Array

Intuition

The naive way is to identify all possible subarrays using nested loops. For each subarray, calculate the product of its elements. Ultimately, return the maximum product found among all subarrays.

Approach

Iterate in the array using i which runs from 0 to sizeOfArray - 1, it will basically identify the starting point of the subarrays.

Now run an inner loop using j from i+1 to sizeOfArray - 1, it will identify the ending point of the subarrays. Inside this loop, iterate again from i to j and multiply elements present in the chosen range.

Update the maximum product after each iteration and finally, return it.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find maximum product subarray
    int maxProduct(vector<int>& nums) {
        
        // Initialize result to minimum possible integer
        int result = INT_MIN; 
        
        // Iterate through all subarrays 
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i; j < nums.size(); j++) {
                int prod = 1;
                
                // Calculate product of subarray 
                for (int k = i; k <= j; k++) {
                    prod *= nums[k];
                }
                
                // Update the result with maximum product found
                result = max(result, prod);
            }
        }
        
        // Return the maximum product found
        return result;
    }
};

int main() {
    vector<int> nums = {4, 5, 3, 7, 1, 2};
    
    // Create an instance of the Solution class
    Solution sol;

    int maxProd = sol.maxProduct(nums);
    
    // Print the result
    cout << "The maximum product subarray: " << maxProd << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to find maximum product subarray
    public int maxProduct(int[] nums) {
        // Initialize result to minimum possible integer
        int result = Integer.MIN_VALUE;

        // Iterate through all subarrays
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                int prod = 1;

                // Calculate product of subarray 
                for (int k = i; k <= j; k++) {
                    prod *= nums[k];
                }

                // Update the result with maximum product found
                result = Math.max(result, prod);
            }
        }

        // Return the maximum product found
        return result;
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {4, 5, 3, 7, 1, 2};

        // Create an instance of the Solution class
        Solution sol = new Solution();

        int maxProd = sol.maxProduct(nums);

        // Print the result
        System.out.println("The maximum product subarray: " + maxProd);
    }
}
class Solution:
    # Function to find the maximum product subarray
    def maxProduct(self, nums):
        # Initialize result to minimum possible integer
        result = float('-inf')

        # Iterate through all subarrays
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                prod = 1

                # Calculate product of subarray 
                for k in range(i, j + 1):
                    prod *= nums[k]

                # Update result with the maximum product found
                result = max(result, prod)

        # Return the maximum product found
        return result

if __name__ == "__main__":
    nums = [4, 5, 3, 7, 1, 2]
    
    # Create an instance of the Solution class
    sol = Solution()
    
    maxProd = sol.maxProduct(nums)

    # Print the result
    print("The maximum product subarray:", maxProd)
class Solution {
    // Function to find the maximum product subarray
    maxProduct(nums) {
        //Initialize result to minimum possible integer
        let result = Number.MIN_SAFE_INTEGER;

        // Iterate through all subarrays using two nested loops
        for (let i = 0; i < nums.length; i++) {
            for (let j = i; j < nums.length; j++) {
                let prod = 1;

                // Calculate product of subarray 
                for (let k = i; k <= j; k++) {
                    prod *= nums[k];
                }

                // Update the result with maximum product found
                result = Math.max(result, prod);
            }
        }

        // Return the maximum product found 
        return result;
    }

    static main() {
        const nums = [4, 5, 3, 7, 1, 2];

        // Create an instance of Solution class
        let sol = new Solution();

        let maxProd = sol.maxProduct(nums);

        // Print the result
        console.log("The maximum product subarray:", maxProd);
    }
}

// Call the main function to test the Solution class
Solution.main();

Complexity Analysis

Time Complexity: O(N³) for using 3 nested loops for finding all possible subarrays and their product. Here N is the size of the array. Space Complexity: O(1), as no additional space is used apart from the input array.

Intuition

A better idea is to maximize the product using two loops. In the innermost loop of the brute-force solution, observe that we calculate the product of subarrays starting from index i to j. However, it can be optimized by computing the product incrementally. Multiplying arr[j] in the second loop with the previous product. This approach improves the time complexity of the solution.

Approach

Iterate in the array using i which starts from 0 and goes till sizeOfArray - 1. Now, iterate in array using an inner loop using j, which starts from i+1 and goes till sizeOfArray - 1. Initialize a variable prod to store product and max to store maximum product.

Inside this loop, multiply arr[j] to prod variable in each iteration and update the max variable each time. Finally, return max variable as an answer.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find maximum product subarray
    int maxProduct(vector<int>& nums) {
        
        // Initialize result with first element of nums
        int result = nums[0]; 
        
        /* Iterate through each element
        as a starting point of subarray*/
        for (int i = 0; i < nums.size(); i++) {
            
            // Initialize p with nums[i]
            int p = nums[i];

            /* Iterate through subsequent elements 
            to form subarrays starting from nums[i]*/
            for (int j = i + 1; j < nums.size(); j++) {
                
                /* Update result with the 
                max of current result and p*/
                result = max(result, p);
                
                // Update p by multiplying with nums[j]
                p *= nums[j]; 
            }
            
            // Update result for subarray ending at nums[i]
            result = max(result, p); 
        }
        
        // Return maximum product subarray found
        return result; 
    }
};

int main() {
    vector<int> nums = {4, 5, 3, 7, 1, 2};
    
    // Create an instance of the Solution class
    Solution sol;
  
    int maxProd = sol.maxProduct(nums);
    
    // Print the result
    cout << "The maximum product subarray: " << maxProd << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to find maximum product subarray
    public int maxProduct(int[] nums) {
        // Initialize result with first element of nums
        int result = nums[0];

        /* Iterate through each element
        as a starting point of subarray */
        for (int i = 0; i < nums.length; i++) {
            // Initialize p with nums[i]
            int p = nums[i];

            /* Iterate through subsequent elements
            to form subarrays starting from nums[i] */
            for (int j = i + 1; j < nums.length; j++) {
                
                /* Update result with the
                max of current result and p */
                result = Math.max(result, p);

                // Update p by multiplying with nums[j]
                p *= nums[j];
            }

            // Update result for subarray ending at nums[i]
            result = Math.max(result, p);
        }

        // Return maximum product subarray found
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 3, 7, 1, 2};

        // Create an instance of the Solution class
        Solution sol = new Solution();

        int maxProd = sol.maxProduct(nums);

        // Print the result
        System.out.println("The maximum product subarray: " + maxProd);
    }
}
class Solution:
    # Function to find maximum product subarray
    def maxProduct(self, nums):
        # Initialize result with first element of nums
        result = nums[0]

        """ Iterate through each element
        as a starting point of subarray """
        for i in range(len(nums)):
            # Initialize p with nums[i]
            p = nums[i]

            """ Iterate through subsequent elements
            to form subarrays starting from nums[i] """
            for j in range(i + 1, len(nums)):
                
                """ Update result with the
                max of current result and p """
                result = max(result, p)

                # Update p by multiplying with nums[j]
                p *= nums[j]

            # Update result for subarray ending at nums[i]
            result = max(result, p)

        # Return maximum product subarray found
        return result

if __name__ == "__main__":
        nums = [4, 5, 3, 7, 1, 2]

        # Create an instance of the Solution class
        sol = Solution()

        maxProd = sol.maxProduct(nums)

        # Print the result
        print("The maximum product subarray:", maxProd)

class Solution {
    /* Function to find maximum product subarray */
    maxProduct(nums) {
        // Initialize result with first element of nums
        let result = nums[0];

        /* Iterate through each element
        as a starting point of subarray */
        for (let i = 0; i < nums.length; i++) {
            
            // Initialize p with nums[i]
            let p = nums[i];

            /* Iterate through subsequent elements
            to form subarrays starting from nums[i] */
            for (let j = i + 1; j < nums.length; j++) {
                
                /* Update result with the
                max of current result and p */
                result = Math.max(result, p);

                // Update p by multiplying with nums[j]
                p *= nums[j];
            }

            // Update result for subarray ending at nums[i]
            result = Math.max(result, p);
        }

        // Return maximum product subarray found
        return result;
    }

    static main() {
        const nums = [4, 5, 3, 7, 1, 2];

        // Create an instance of Solution class
        let sol = new Solution();

        let maxProd = sol.maxProduct(nums);

        // Print the result
        console.log("The maximum product subarray:", maxProd);
    }
}

// Call the main function to test the Solution class
Solution.main();

Complexity Analysis

Time Complexity: O(N²) for using 2 nested loops for finding all possible subarrays and their product. Here N is the size of the array. Space Complexity: O(1) as no additional space is used apart from the input array.

Intuition:

The goal is to find the subarray having the maximum product of elements. To solve the problem efficiently, we need to understand the following points:

The product of an even number of negative numbers result in a positive product, whereas the product of an odd number of negative numbers result in a negative product.
If an array element is zero, considering it in the subarray will result in product as 0, giving the idea of skipping it.

The multiplication of all the elements in the array could have been our answer if there were all positives or even negatives in the array (with no element as 0) but the problem arises when there are odd number of negative elements in the array.

Understanding:

When the array has an odd number of negative elements, one must be excluded to make their product positive. Since the subarray must be contiguous, only the first or last negative element can be removed. By calculating the product from both directions — prefix and suffix — we can determine the maximum product subarray.

When there are zeroes in the array?

When there are zeroes in the array, the prefix and suffix will end up becoming zero. Hence, whenever the prefix or the suffix are found to be zero, it means that a zero element was found meaning that we must reassign them with the value 1.
Note that the two-directional traversal (prefix and suffix) is achieved within a single loop, avoiding the need for separate iterations. This makes the solution more efficient while maintaining simplicity.

Approach:

Initialize a variable to store the maximum product result.
Maintain two running products: one for the prefix (left to right traversal) and one for the suffix (right to left traversal).
Iterate through the array:
- If the running product becomes zero, reset it to one to start a new subarray.
- Update the prefix product with the current element during the left-to-right traversal.
- Update the suffix product with the current element during the right-to-left traversal.
At each step, compute the maximum product using the current prefix and suffix products.
Return the maximum product obtained after the traversal.

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the product of
    elements in maximum product subarray */
	int maxProduct(vector<int>& nums) {
	    int n = nums.size();
	    
	    int ans = INT_MIN; // to store the answer
	    
	    // Indices to store the prefix and suffix multiplication
        int prefix = 1, suffix = 1;
        
        // Iterate on the elements of the given array
        for(int i=0; i < n; i++) {
            
            /* Resetting the prefix and suffix
            multiplication if they turn out to be zero */
            if(prefix == 0) prefix = 1;
            if(suffix == 0) suffix = 1;
            
            // update the prefix and suffix multiplication
            prefix *= nums[i];
            suffix *= nums[n-i-1];
            
            // store the maximum as the answer
            ans = max(ans, max(prefix, suffix));
        }
        
        // return the result
        return ans;
	}
};

int main() {
	vector<int> nums = {4, 5, 3, 7, 1, 2};

	// Creating an object of Solution class
	Solution sol;

	/* Function call to find the product of
	elements in maximum product subarray */
	int ans = sol.maxProduct(nums);

	cout << "The product of elements in maximum product subarray is: " << ans;

	return 0;
}
class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        
        int ans = Integer.MIN_VALUE; // to store the answer
        
        // Indices to store the prefix and suffix multiplication
        int prefix = 1, suffix = 1;
        
        // Iterate on the elements of the given array
        for (int i = 0; i < n; i++) {
            
            /* Resetting the prefix and suffix
            multiplication if they turn out to be zero */
            if (prefix == 0) prefix = 1;
            if (suffix == 0) suffix = 1;
            
            // update the prefix and suffix multiplication
            prefix *= nums[i];
            suffix *= nums[n - i - 1];
            
            // store the maximum as the answer
            ans = Math.max(ans, Math.max(prefix, suffix));
        }
        
        // return the result
        return ans;
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {4, 5, 3, 7, 1, 2};
        
        // Creating an object of Solution class
        Solution sol = new Solution();
        
        /* Function call to find the product of
        elements in maximum product subarray */
        int ans = sol.maxProduct(nums);
        
        System.out.println("The product of elements in maximum product subarray is: " + ans);
    }
}
class Solution:
    # Function to find the product of elements in maximum product subarray
    def maxProduct(self, nums):
        n = len(nums)
        
        ans = float('-inf') # to store the answer
        
        # Indices to store the prefix and suffix multiplication
        prefix, suffix = 1, 1
        
        # Iterate on the elements of the given array
        for i in range(n):
            
            # Resetting the prefix and suffix multiplication if they turn out to be zero
            if prefix == 0: 
                prefix = 1
            if suffix == 0: 
                suffix = 1
            
            # update the prefix and suffix multiplication
            prefix *= nums[i]
            suffix *= nums[n - i - 1]
            
            # store the maximum as the answer
            ans = max(ans, max(prefix, suffix))
        
        # return the result
        return ans

# Example usage
nums = [4, 5, 3, 7, 1, 2]
sol = Solution()
ans = sol.maxProduct(nums)
print("The product of elements in maximum product subarray is:", ans)
class Solution {
    /* Function to find the product of 
    elements in maximum product subarray */
    maxProduct(nums) {
        let n = nums.length;
        
        let ans = Number.MIN_SAFE_INTEGER; // to store the answer
        
        // Indices to store the prefix and suffix multiplication
        let prefix = 1, suffix = 1;
        
        // Iterate on the elements of the given array
        for (let i = 0; i < n; i++) {
            
            /* Resetting the prefix and suffix
            multiplication if they turn out to be zero */
            if (prefix === 0) prefix = 1;
            if (suffix === 0) suffix = 1;
            
            // update the prefix and suffix multiplication
            prefix *= nums[i];
            suffix *= nums[n - i - 1];
            
            // store the maximum as the answer
            ans = Math.max(ans, prefix, suffix);
        }
        
        // return the result
        if(ans === -0) return 0;
        return ans;
    }
}

// Example usage
let nums = [4, 5, 3, 7, 1, 2];
let sol = new Solution();
let ans = sol.maxProduct(nums);
console.log("The product of elements in maximum product subarray is:", ans);

Complexity Analysis:

Time Complexity: O(N), where N is the size of the array
Traversing the given array using single for loop takes linear time.

Space Complexity: O(1), as only couple of variables are used.

Problem List

Maximum Product Subarray in an Array

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Complexity Analysis

Intuition

Approach

Complexity Analysis

Intuition:

Understanding:

When there are zeroes in the array?

Approach:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code