# Maximum Product Subarray

## Introduction

In this article, you will learn ways to find the maximum product subarray. We will start with a brute force approach and then see ideas by which we can optimize the solution along with implementation in C++.

The problem statement is as follows:

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

Subarray - A contiguous subsequence of an array is called a subarray.

Example - Given an array [1,2,3,5,6], some of the subarrays are ,,,,[1,2,3], [3,5,6] etc.

I strongly recommend giving an honest try at this problem and solve it by yourself before moving on to further discussions. You can solve it here - Maximum Product Subarray

## Initial thoughts about solving the problem

• It is an integer array i.e, the array may contain positivenegative and even zero integers.
• Next, we have to deal with subarrays, so we can choose only contiguous segments of the array.
• (Negative integer)*(Negative integer) = Positive integer ( I know, it may sound a bit childish to write this point but if you think about it, you realize it’s a key point for this problem).
• (Positive integer)*(Negative integer) = Negative integer
• (Positive integer)*(Positive integer) = Positive integer

## Brute Force Method

We will first come up with a brute force approach to solve the problem.

Let’s see the steps to be followed -

1. Define a variable maximum_product to store the maximum product of the subarray found so far.
2. Initialize maximum_product to INT_MIN.
3. We generate all the subarrays one by one and find the respective product of the subarray.
4. For every subarray found, we will update the maximum product when the current product is greater than the current maximum product.

## C++ Implementation

Output:

### Time Complexity - O(n^2)

Since we check the product of all the subarrays for which we have used two loops. So, the time complexity is O(n^2).

### Space Complexity - O(1)

We have not used any extra space to find the maximum product subarray. So, it has constant space complexity.

## How to optimize?

If you know about Kadane’s Algorithm, then this problem is quite similar to this except for in this we have to find maximum product subarray instead of subarray sum.

### Algorithm

• Traverse the array and calculate the maximum and minimum product ending at the current index.
• Update the result if the maximum product ending at any index is greater than the maximum product found so far.

For every index we have three possibilities:

• When the current element is positive, then we may get the maximum product by the multiplication of the current number and the maximum product ending at the previous index.
• When the current element is negative, then the product of the minimum product ending at the previous index and the current number might give the maximum product.
• The maximum product subarray may start from the current index.

### Time Complexity - O(n)

We iterate over the given array only once to find the maximum product subarray, so the time complexity is O(n), where n is the number of elements in the array.

### Space Complexity - O(1)

The algorithm does not use any extra space, so the space complexity is O(1).

## Key Takeaways

In this article, we discussed the solution to find the maximum product subarray. We saw two approaches: brute force method and then optimized it to get a solution with linear time complexity. The problem was quite similar to the famous Kadane’s Algorithm. You can check it out to understand better.

Planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on CodeStudio now! 