.png)
Maximum Product Subarray
Problem Statement
You are given an integer array arr.
Find the contiguous subarray (containing at least one number) which has the maximum product, and return that product.
Example 1
Input
arr = [2, 3, -2, 4]
Output
6
Explanation
Subarray [2, 3] gives maximum product = 6
Example 2
Input
arr = [-2, 0, -1]
Output
0
Why This Problem Is Important
- Very frequently asked interview problem
- Tests handling of negative numbers
- Tests dynamic programming thinking
- Edge cases with zero and sign flips
- Appears in FAANG interviews
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Prefix & Suffix Product | O(n) | O(1) |
| Approach 3 | Kadane’s Variant (Optimal) | O(n) | O(1) |
Approach 1: Brute Force
Idea
Calculate product of every possible subarray and track the maximum.
Algorithm
- Initialize maxProduct = -∞
- For each starting index i
- Multiply elements from i to j
- Update maxProduct
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
Implementations
C
#include
#include
int main() {
int arr[] = {2,3,-2,4};
int n = 4;
int maxProduct = INT_MIN;
for(int i = 0; i < n; i++) {
int prod = 1;
for(int j = i; j < n; j++) {
prod *= arr[j];
if(prod > maxProduct)
maxProduct = prod;
}
}
printf("%d", maxProduct);
return 0;
}
C++
#include
#include
using namespace std;
int main() {
int arr[] = {2,3,-2,4};
int n = 4;
int maxProduct = INT_MIN;
for(int i = 0; i < n; i++) {
int prod = 1;
for(int j = i; j < n; j++) {
prod *= arr[j];
maxProduct = max(maxProduct, prod);
}
}
cout << maxProduct;
return 0;
}
Java
public class MaxProductSubarray {
public static void main(String[] args) {
int[] arr = {2,3,-2,4};
int maxProduct = Integer.MIN_VALUE;
for(int i = 0; i < arr.length; i++) {
int prod = 1;
for(int j = i; j < arr.length; j++) {
prod *= arr[j];
maxProduct = Math.max(maxProduct, prod);
}
}
System.out.print(maxProduct);
}
}
Python
arr = [2,3,-2,4]
maxProduct = float('-inf')
for i in range(len(arr)):
prod = 1
for j in range(i, len(arr)):
prod *= arr[j]
maxProduct = max(maxProduct, prod)
print(maxProduct)
JavaScript
let arr = [2,3,-2,4];
let maxProduct = -Infinity;
for (let i = 0; i < arr.length; i++) {
let prod = 1;
for (let j = i; j < arr.length; j++) {
prod *= arr[j];
maxProduct = Math.max(maxProduct, prod);
}
}
console.log(maxProduct);
Approach 2: Prefix & Suffix Product
Idea
Because negatives flip signs, compute product from left to right and right to left, resetting on zero.
Algorithm
- Initialize maxProduct, prefix = 1, suffix = 1
- Traverse array from left
- prefix *= arr[i]
- Update max
- Reset prefix if zero
- Traverse from right
- Same logic using suffix
Time & Space Complexity
- Time: O(n)
- Space: O(1)
Implementations
C++
#include
#include
using namespace std;
int main() {
int arr[] = {2,3,-2,4};
int n = 4;
int maxProduct = INT_MIN;
int prefix = 1, suffix = 1;
for(int i = 0; i < n; i++) {
prefix = (prefix == 0 ? 1 : prefix) * arr[i];
suffix = (suffix == 0 ? 1 : suffix) * arr[n - i - 1];
maxProduct = max(maxProduct, max(prefix, suffix));
}
cout << maxProduct;
return 0;
}
Java
public class MaxProductSubarray {
public static void main(String[] args) {
int[] arr = {2,3,-2,4};
int maxProduct = Integer.MIN_VALUE;
int prefix = 1, suffix = 1;
int n = arr.length;
for(int i = 0; i < n; i++) {
prefix = (prefix == 0 ? 1 : prefix) * arr[i];
suffix = (suffix == 0 ? 1 : suffix) * arr[n - i - 1];
maxProduct = Math.max(maxProduct, Math.max(prefix, suffix));
}
System.out.print(maxProduct);
}
}
Python
arr = [2,3,-2,4]
maxProduct = float('-inf')
prefix = suffix = 1
n = len(arr)
for i in range(n):
prefix = (prefix if prefix != 0 else 1) * arr[i]
suffix = (suffix if suffix != 0 else 1) * arr[n - i - 1]
maxProduct = max(maxProduct, prefix, suffix)
print(maxProduct)
JavaScript
let arr = [2,3,-2,4];
let maxProduct = -Infinity;
let prefix = 1, suffix = 1;
for (let i = 0; i < arr.length; i++) {
prefix = (prefix === 0 ? 1 : prefix) * arr[i];
suffix = (suffix === 0 ? 1 : suffix) * arr[arr.length - i - 1];
maxProduct = Math.max(maxProduct, prefix, suffix);
}
console.log(maxProduct);
_1770825380.png)
Approach 3: Kadane’s Variant (Optimal)
Idea
Track both:
- maxEndingHere
- minEndingHere
Because a negative number can turn a minimum product into a maximum.
Algorithm
- Initialize
- maxEnding = arr[0]
- minEnding = arr[0]
- result = arr[0]
- Traverse from index 1
- If arr[i] < 0, swap max & min
- Update maxEnding
- Update minEnding
- Update result
Time & Space Complexity
- Time: O(n)
- Space: O(1)
Implementations
C
#include
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
int main() {
int arr[] = {2,3,-2,4};
int n = 4;
int maxEnding = arr[0];
int minEnding = arr[0];
int result = arr[0];
for(int i = 1; i < n; i++) {
if(arr[i] < 0) {
int temp = maxEnding;
maxEnding = minEnding;
minEnding = temp;
}
maxEnding = max(arr[i], maxEnding * arr[i]);
minEnding = min(arr[i], minEnding * arr[i]);
result = max(result, maxEnding);
}
printf("%d", result);
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {2,3,-2,4};
int n = 4;
int maxEnding = arr[0];
int minEnding = arr[0];
int result = arr[0];
for(int i = 1; i < n; i++) {
if(arr[i] < 0)
swap(maxEnding, minEnding);
maxEnding = max(arr[i], maxEnding * arr[i]);
minEnding = min(arr[i], minEnding * arr[i]);
result = max(result, maxEnding);
}
cout << result;
return 0;
}
Java
public class MaxProductSubarray {
public static void main(String[] args) {
int[] arr = {2,3,-2,4};
int maxEnding = arr[0];
int minEnding = arr[0];
int result = arr[0];
for(int i = 1; i < arr.length; i++) {
if(arr[i] < 0) {
int temp = maxEnding;
maxEnding = minEnding;
minEnding = temp;
}
maxEnding = Math.max(arr[i], maxEnding * arr[i]);
minEnding = Math.min(arr[i], minEnding * arr[i]);
result = Math.max(result, maxEnding);
}
System.out.print(result);
}
}
Python
arr = [2,3,-2,4]
maxEnding = minEnding = result = arr[0]
for i in range(1, len(arr)):
if arr[i] < 0:
maxEnding, minEnding = minEnding, maxEnding
maxEnding = max(arr[i], maxEnding * arr[i])
minEnding = min(arr[i], minEnding * arr[i])
result = max(result, maxEnding)
print(result)
JavaScript
let arr = [2,3,-2,4];
let maxEnding = arr[0];
let minEnding = arr[0];
let result = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < 0)
[maxEnding, minEnding] = [minEnding, maxEnding];
maxEnding = Math.max(arr[i], maxEnding * arr[i]);
minEnding = Math.min(arr[i], minEnding * arr[i]);
result = Math.max(result, maxEnding);
}
console.log(result);
Dry Run (Kadane’s Variant)
Input
[2, 3, -2, 4]
| Element | maxEnding | minEnding | result |
|---|---|---|---|
| 2 | 2 | 2 | 2 |
| 3 | 6 | 3 | 6 |
| -2 | -2 | -12 | 6 |
| 4 | 4 | -48 | 6 |
Summary
- Brute force is inefficient
- Prefix–suffix handles sign changes
- Kadane’s variant is optimal and interview-preferred
- Handles negatives and zero efficiently
Next Problem in the Series
Find the First Missing Positive Integer
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
