# Maximum Product Subarray

Difficulty Level Medium
Array Dynamic ProgrammingViews 1850

Given an array of n integers, find the maximum product obtained from a contiguous subarray of the given array.

## Examples

Input
arr[] = {-2, -3, 0, -2, -40}
Output
80

Input
arr[] = {5, 10, 6, -2, 1}
Output
300

Input
arr[] = {-1, -4, -10, 0, 70}
Output
70

## Algorithm for Maximum Product Subarray

The given problem is a variation of Kadane’s Algorithm, define three variables maxTillNow, minTillNow and max, where,
maxTillNow –> Maximum Product up to this index, including this index
minTillNow –> Minimum Product up to this index, including this index
max –> The maximum product

1. Initialize maxTillNow, minTillNow and max as arr[0].
2. Traverse the array starting from index 1.
3. If the current element is negative swap maxTillNow and minTillNow.
4. Update maxTillNow as maximum of arr[i] and (maxTillNow * arr[i]).
5. Update minTillNow as minimum of arr[i] and (minTillNow * arr[i]).
6. Also, update max as a maximum of max and maxTillNow.
7. At the end of traversal, return max.

## Explanation for Maximum Product Subarray

Consider an example,
arr[] = {5, 10, 6, -2, 1}

Step 1

maxTillNow = 5, minTillNow = 5 and max = 5

Step 2

Repeat steps 3 to 6.

Steps 3 to 6

Iteration 1
arr[1] = 10
maxTillNow = 5 and minTillNow = 5
Update maxTillNow,
maxTillNow = maximum(arr[1], maxTillNow * arr[1]) = 50
Update minTillNow,
minTillNow = minimum(arr[1], minTillNow * arr[1] = 10
Update max,
max = maximum(max, maxTillNow) = 50

Iteration 2
arr[2] = 6
maxTillNow = 50 and minTillNow = 10
Update maxTillNow,
maxTillNow = maximum(arr[2], maxTillNow * arr[2]) = 300
Update minTillNow,
minTillNow = minimum(arr[2], minTillNow * arr[2]) = 6
Update max,
max = maximum(max, maxTillNow) = 300

Iteration 3
arr[3] = -2
maxTillNow = 6 and minTillNow = 300 (Swap as arr[3] is negative)
Update maxTillNow,
maxTillNow = maximum(arr[3], maxTillNow * arr[3]) = -2
Update minTillNow,
minTillNow = minimum(arr[3], minTillNow * arr[3]) = -600
Update max,
max = maximum(max, maxTillNow) = 300

Iteration 4
arr[4] = 1
maxTillNow = -2 and minTillNow = -600
Update maxTillNow,
maxTillNow = maximum(arr[4], maxTillNow * arr[4]) = 1
Update minTillNow,
minTillNow = minimum(arr[4], minTillNow * arr[4]) = -600
Update max,
max = maximum(max, maxTillNow) = 300

Step 7

The maximum value product subarray value is 300.

## JAVA Code for Maximum Product Subarray

```public class MaximumProductSubarray {
private static int maxProduct(int[] arr) {
int n = arr.length;
// Initialise maxTillNow, minTillNow and max as arr[0]
int maxTillNow = arr[0], minTillNow = arr[0], max = arr[0];
// Start traversing the array from index 1
for (int i = 1; i < n; i++) {
// If current element is negative, swap maxTillNow and minTillNow
if (arr[i] < 0) {
int temp = maxTillNow;
maxTillNow = minTillNow;
minTillNow = temp;
}

// Update maxTillNow as maximum of arr[i] and (arr[i] * maxTillNow)
maxTillNow = Math.max(arr[i], arr[i] * maxTillNow);
// Update minTillNow as minimum of arr[i] and (arr[i] * minTillNow)
minTillNow = Math.min(arr[i], arr[i] * minTillNow);

// Update max as maximum of max and maxTillNow
max = Math.max(max, maxTillNow);
}

// return max
return max;
}

public static void main(String[] args) {
// Example 1
int arr[] = new int[] {-2, -3, 0, -2, -40};
System.out.println(maxProduct(arr));

// Example 2
int arr2[] = new int[] {5, 10, 6, -2, 1};
System.out.println(maxProduct(arr2));

// Example 3
int arr3[] = new int[] {-1, -4, -10, 0, 70};
System.out.println(maxProduct(arr3));
}
}```

## C++ Code for Maximum Product Subarray

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

int maxProduct(int *arr, int n) {
// Initialise maxTillNow, minTillNow and max as arr[0]
int maxTillNow = arr[0], minTillNow = arr[0], max = arr[0];
// Start traversing the array from index 1
for (int i = 1; i < n; i++) {
// If current element is negative, swap maxTillNow and minTillNow
if (arr[i] < 0) {
int temp = maxTillNow;
maxTillNow = minTillNow;
minTillNow = temp;
}

// Update maxTillNow as maximum of arr[i] and (arr[i] * maxTillNow)
maxTillNow = std::max(arr[i], arr[i] * maxTillNow);
// Update minTillNow as minimum of arr[i] and (arr[i] * minTillNow)
minTillNow = std::min(arr[i], arr[i] * minTillNow);

// Update max as maximum of max and maxTillNow
max = std::max(max, maxTillNow);
}

// return max
return max;
}

int main() {
// Example 1
int arr[] = {-2, -3, 0, -2, -40};
cout<<maxProduct(arr, 5)<<endl;

// Example 2
int arr2[] = {5, 10, 6, -2, 1};
cout<<maxProduct(arr2, 5)<<endl;

// Exmaple 3
int arr3[] = {-1, -4, -10, 0, 70};
cout<<maxProduct(arr3, 5)<<endl;

return 0;
}```
```80
300
70```

## Complexity Analysis

Time Complexity = O(n)
Space Complexity = O(1)
where n is the number of elements in the array.

References

Translate »