# 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 **A **= **[1,2,3,5,6]**, some of the subarrays are [1],[2],[3],[6],[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
**positive**,**negative**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 -

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

## C++ Implementation

/* C++ code to find maximum product subarray of an array */#include <iostream>using namespace std;/* function to find the maximum product of a subarray for a given array */int findMaximumProduct(int arr[], int n){ /* to store the maximum product subarray found so far */ int max_so_far = 0; /* consider all subarrays starting from i */ for (int i = 0; i < n; i++) { /* to store the current subarray product */ int product = 1; /* consider all subarrays ending at j */ for (int j = i; j < n; j++) { /* product of elements of the subarray arr[i,j] */ product *= arr[j]; /* update the maximum product if required */ if (product > max_so_far) { max_so_far = product; } } } return max_so_far;}int main(){ int arr[] = {6, -4, -5, 8, 0, 7}; int n = sizeof(arr) / sizeof(arr[0]); cout << "The maximum product subarray is " << findMaximumProduct(arr, n)<<endl; return 0;} |

**Output:**

The maximum product subarray is 960 |

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

### C++ Implementation

/* C++ code to find maximum product subarray of an array */#include <bits/stdc++.h>using namespace std;/* function to find the maximum product of a subarray from given array*/int findMaxProduct(int arr[], int n){ /* define two variables to store the maximum and minimum product ending at the current index */ int max_ending = arr[0], min_ending = arr[0]; /* stores the maximum product subarray found so far */ int max_so_far = arr[0]; /* traverse the array */ for (int i = 1; i < n; i++) { int temp = max_ending; /* update the maximum product ending at the current index*/ max_ending = max(arr[i], max(arr[i] * max_ending, arr[i] * min_ending)); /* update the minimum product ending at the current index*/ min_ending = min(arr[i], min(arr[i] * temp, arr[i] * min_ending)); max_so_far = max(max_so_far, max_ending); } return max_so_far;}int main(void){ int arr[] = {6, -4, -5, 8, 0, 7}; int n = sizeof(arr) / sizeof(arr[0]); cout << "The maximum product of a subarray is: " << findMaxProduct(arr, n) << endl; return 0;} |

Output:The maximum product of a subarray is: 960 |

### 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!**

Comments

## No comments yet

## Be the first to share what you think