Maximum Product Subarray
Maximum Product Subarray Problem
Given an integer array nums, find the subarray with the maximum product and return its value.
A sub array is a continuous, non-empty portion of the array.
You can assume the result will fit within a 32-bit integer.
Example 1:
Input: nums = [-2,-1]
Output: 2
Output: 2
Example 2:
Input: nums = [1,2,-3,4]
Output: 4
Output: 4
Constraints:
- 1 <= nums.length <= 1000
- -10 <= nums[i] <= 10
Maximum Product Subarray Solution
Approaches for solving Maximum Product Subarray problem
There are mainly 4 approach to solve this problem
- Brute Force Method
- Sliding Window Method
- Kadane’s Algorithm Method
- Prefix & Suffix
1. Brute Force Method:
Check all possible subarrays in the array, calculate their products, and track the maximum product found. This method is simple but inefficient for large arrays as it checks every combination.
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0];
for (int i = 0; i < nums.size(); i++) {
int cur = nums[i];
res = max(res, cur);
for (int j = i + 1; j < nums.size(); j++) {
cur *= nums[j];
res = max(res, cur);
}
}
return res;
}
};
Java
public class Solution {
public int maxProduct(int[] nums) {
int res = nums[0];
for (int i = 0; i < nums.length; i++) {
int cur = nums[i];
res = Math.max(res, cur);
for (int j = i + 1; j < nums.length; j++) {
cur *= nums[j];
res = Math.max(res, cur);
}
}
return res;
}
}
Python
class Solution:
def maxProduct(self, nums: List[int]) -> int:
res = nums[0]
for i in range(len(nums)):
cur = nums[i]
res = max(res, cur)
for j in range(i + 1, len(nums)):
cur *= nums[j]
res = max(res, cur)
return res
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
maxProduct(nums) {
let res = nums[0];
for (let i = 0; i < nums.length; i++) {
let cur = nums[i];
res = Math.max(res, cur);
for (let j = i + 1; j < nums.length; j++) {
cur *= nums[j];
res = Math.max(res, cur);
}
}
return res;
}
}
2. Sliding Window Method
Use a sliding window to iterate through the array while keeping track of the current product, updating it as you move the window. This approach is faster but still needs care with negative numbers.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int maxProduct(vector<int>& nums) {
vector<vector<int>> A;
vector<int> cur;
int res = INT_MIN;
for (auto& num : nums) {
res = max(res, num);
if (num == 0) {
if (!cur.empty()) A.push_back(cur);
cur.clear();
} else cur.push_back(num);
}
if (!cur.empty()) {
A.push_back(cur);
}
for (auto& sub : A) {
int negs = 0;
for (auto& i : sub) {
if (i < 0) negs++;
}
int prod = 1;
int need = (negs % 2 == 0) ? negs : (negs - 1);
negs = 0;
for (int i = 0, j = 0; i < sub.size(); i++) {
prod *= sub[i];
if (sub[i] < 0) { negs++; while (negs > need) {
prod /= sub[j];
if (sub[j] < 0) negs--;
j++;
}
}
if (j <= i) res = max(res, prod);
}
}
return res;
}
};
Java
public class Solution {
public int maxProduct(int[] nums) {
List<List<Integer>> A = new ArrayList<>();
List<Integer>cur = new ArrayList<>();
int res = Integer.MIN_VALUE;
for (int num : nums) {
res = Math.max(res, num);
if (num == 0) {
if (!cur.isEmpty()) A.add(cur);
cur = new ArrayList<>();
} else cur.add(num);
}
if (!cur.isEmpty()) A.add(cur);
for (List<Integer> sub : A) {
int negs = 0;
for (int i : sub) {
if (i < 0) negs++;
}
int prod = 1;
int need = (negs % 2 == 0) ? negs : (negs - 1);
negs = 0;
for (int i = 0, j = 0; i < sub.size(); i++) {
prod *= sub.get(i);
if (sub.get(i) < 0) { negs++; while (negs > need) {
prod /= sub.get(j);
if (sub.get(j) < 0) negs--;
j++;
}
}
if (j <= i) res = Math.max(res, prod);
}
}
return res;
}
}
Python
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
maxProduct(nums) {
let A = [];
let cur = [];
let res = -Infinity;
nums.forEach(num => {
res = Math.max(res, num);
if (num === 0) {
if (cur.length) A.push(cur);
cur = [];
} else {
cur.push(num);
}
});
if (cur.length) A.push(cur);
A.forEach(sub => {
let negs = 0;
sub.forEach(i => {
if (i < 0) negs++;
});
let prod = 1;
let need = (negs % 2 === 0) ? negs : (negs - 1);
negs = 0;
for (let i = 0, j = 0; i < sub.length; i++) {
prod *= sub[i];
if (sub[i] < 0) {
negs++;
while (negs > need) {
prod /= sub[j];
if (sub[j] < 0) negs--;
j++;
}
}
if (j <= i) res = Math.max(res, prod);
}
});
return res;
}
}
JavaScript
class Solution {
/**
* @param {string} s
* @return {number}
*/
countSubstrings(s) {
let res = 0;
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(false));
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
if (s[i] === s[j] &&
(j - i <= 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
res++;
}
}
}
return res;
}
}
3. Kadane’s Algorithm
Modify Kadane’s algorithm to handle products by keeping track of both the maximum and minimum products at each index. This efficiently handles both positive and negative numbers.
- Time complexity: O(n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0];
int curMin = 1, curMax = 1;
for (int num : nums) {
int tmp = curMax * num;
curMax = max(max(num * curMax, num * curMin), num);
curMin = min(min(tmp, num * curMin), num);
res = max(res, curMax);
}
return res;
}
};
Java
public class Solution {
public int maxProduct(int[] nums) {
int res = nums[0];
int curMin = 1, curMax = 1;
for (int num : nums) {
int tmp = curMax * num;
curMax = Math.max(Math.max(num * curMax, num * curMin), num);
curMin = Math.min(Math.min(tmp, num * curMin), num);
res = Math.max(res, curMax);
}
return res;
}
}
Python
class Solution:
def maxProduct(self, nums: List[int]) -> int:
res = nums[0]
curMin, curMax = 1, 1
for num in nums:
tmp = curMax * num
curMax = max(num * curMax, num * curMin, num)
curMin = min(tmp, num * curMin, num)
res = max(res, curMax)
return res
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
maxProduct(nums) {
let res = nums[0];
let curMin = 1;
let curMax = 1;
for (const num of nums) {
const tmp = curMax * num;
curMax = Math.max(Math.max(num * curMax, num * curMin), num);
curMin = Math.min(Math.min(tmp, num * curMin), num);
res = Math.max(res, curMax);
}
return res;
}
}
4. Prefix and Suffix Method
Precompute prefix and suffix products for the array, then find the maximum product by checking combinations of these values. This method reduces time complexity but uses extra space.
- Time complexity: O(n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size(), res = nums[0];
int prefix = 0, suffix = 0;
for (int i = 0; i < n; i++) {
prefix = nums[i] * (prefix == 0 ? 1 : prefix);
suffix = nums[n - 1 - i] * (suffix == 0 ? 1 : suffix);
res = max(res, max(prefix, suffix));
}
return res;
}
};
Java
public class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int res = nums[0];
int prefix = 0, suffix = 0;
for (int i = 0; i < n; i++) {
prefix = nums[i] * (prefix == 0 ? 1 : prefix);
suffix = nums[n - 1 - i] * (suffix == 0 ? 1 : suffix);
res = Math.max(res, Math.max(prefix, suffix));
}
return res;
}
}
Python
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n, res = len(nums), nums[0]
prefix = suffix = 0
for i in range(n):
prefix = nums[i] * (prefix or 1)
suffix = nums[n - 1 - i] * (suffix or 1)
res = max(res, max(prefix, suffix))
return res
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
maxProduct(nums) {
let n = nums.length, res = nums[0];
let prefix = 0, suffix = 0;
for (let i = 0; i < n; i++) {
prefix = nums[i] * (prefix === 0 ? 1 : prefix);
suffix = nums[n - 1 - i] * (suffix === 0 ? 1 : suffix);
res = Math.max(res, Math.max(prefix, suffix));
}
return res === -0 ? 0 : res;
}
}
