Maximum Product Subarray: Find the Largest Product

59.9k
0

Given an integer array nums, return the maximum product of a non-empty contiguous subarray.

A contiguous subarray contains consecutive elements from the original array.

Return 0 when nums is empty.

Example 1

Input: nums = [2, 3, -2, 4]

Output: 6

Explanation: The subarray [2, 3] has product 2 × 3 = 6, which is the maximum product

Example 2

Input: nums = [-2, 0, -1]

Output: 0

Explanation: The subarray [0] gives product 0. The product of [-2, 0, -1] is 0, and no subarray gives a product greater than 0.

Brute Force Approach

The most direct idea is to generate every possible contiguous subarray and calculate the product of all elements inside each selected range.

Checking every range guarantees the correct answer. However, overlapping subarrays repeatedly multiply many of the same elements, making the approach expensive.

Algorithm

  • Store the array size in n. If n == 0, return 0 because no non-empty subarray can be formed.

  • Initialize maxProduct with nums[0], ensuring that the answer always represents a valid subarray even when the array contains only negative values.

  • Treat every index start as the beginning of a possible subarray and every index end from start to n - 1 as its ending position.

  • For each range [start, end], initialize currentProduct with 1 and multiply all elements from start through end to calculate that subarray's product.

  • Compare currentProduct with maxProduct after the complete range has been processed, and update maxProduct whenever a larger product is found.

  • Return maxProduct after every possible contiguous subarray has been examined.

Dry Run

Maximum Product Subarray Brute Force Aprroach.png

Maximum Product Subarray Brute Force Aprroach.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long maxProduct(vector<int>& nums) {
int n = nums.size();
// No non-empty subarray exists.
if (n == 0) {
return 0;
}
long long maxProduct = nums[0];
/*
* Generate every possible subarray
* using its start and end indices.
*/
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
long long currentProduct = 1;
// Calculate the product of the selected range.
for (int index = start; index <= end; index++) {
currentProduct *= nums[index];
}
// Keep the largest product found so far.
if (currentProduct > maxProduct) {
maxProduct = currentProduct;
}
}
}
return maxProduct;
}
};
int main() {
vector<int> nums = {2, 3, -2, 4};
Solution solution;
cout << solution.maxProduct(nums) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N³), where N represents the array size. Two loops select the starting and ending indices, while a third traversal calculates the product of every selected range.

Space Complexity: O(1), because only index variables, currentProduct, and maxProduct require auxiliary storage.

Better Approach

The Brute Force Approach recalculates every selected subarray product from the beginning.

For one fixed starting position, the next subarray contains all previously selected elements plus one new ending element. A running product can therefore reuse the previous result and avoid multiplying the complete range again.

Algorithm

  • Store the array size in n. If the array is empty, return 0.

  • Initialize maxProduct with nums[0] so the result remains valid even when every possible product is negative.

  • Treat every index start as the beginning of a new group of subarrays and initialize currentProduct with 1 for that starting position.

  • Move end from start to n - 1 and multiply currentProduct by nums[end]. This extends the previous range by one element instead of recalculating its complete product.

  • Compare the updated currentProduct with maxProduct after every extension because each value represents the product of one valid subarray.

  • Return maxProduct after all starting and ending positions have been processed.

Dry Run

Maximum Product Subarray Better Aprroach.png

Maximum Product Subarray Better Aprroach.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long maxProduct(vector<int>& nums) {
int n = nums.size();
// No non-empty subarray exists.
if (n == 0) {
return 0;
}
long long maxProduct = nums[0];
for (int start = 0; start < n; start++) {
long long currentProduct = 1;
/*
* Extend the current subarray one element
* at a time and reuse its previous product.
*/
for (int end = start; end < n; end++) {
currentProduct *= nums[end];
// Keep the best product among all ranges seen so far.
if (currentProduct > maxProduct) {
maxProduct = currentProduct;
}
}
}
return maxProduct;
}
};
int main() {
vector<int> nums = {2, 3, -2, 4};
Solution solution;
cout << solution.maxProduct(nums) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N²), where N represents the array size. Every starting index extends through all possible ending indices, while each extension requires only one multiplication.

Space Complexity: O(1), because only loop indices, currentProduct, and maxProduct require auxiliary storage.

Optimal Approach

Products behave differently from sums because a negative value can completely reverse the situation.

The largest positive product can become the smallest negative product after multiplication by a negative value. In the same way, the smallest negative product can suddenly become the largest positive product.

Therefore, both the maximum and minimum products ending at the current position must be remembered. A zero is also handled naturally because starting again from the current value remains one of the available choices.

Algorithm

  • Store the array size in n. If n == 0, return 0.

  • Initialize currentMax, currentMin, and maxProduct with nums[0]. currentMax stores the largest product ending at the current position, while currentMin keeps the smallest product that may become useful after multiplication by a negative value.

  • Traverse from index 1, since the first element has already been used to build the initial state.

  • Store the previous values of currentMax and currentMin before updating them, because both new states must be calculated from the same previous position.

  • For the current value, consider three possibilities: start a new subarray from the current element, extend the previous maximum product, or extend the previous minimum product. Store the largest result in currentMax and the smallest in currentMin.

  • Update maxProduct using currentMax after every position, then return maxProduct once the entire array has been processed.

Dry Run

Maximum Product Subarray Optimal Aprroach Dry Run.png

Maximum Product Subarray Optimal Aprroach Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long maxProduct(vector<int>& nums) {
int n = nums.size();
// No non-empty subarray exists.
if (n == 0) {
return 0;
}
long long currentMax = nums[0];
long long currentMin = nums[0];
long long maxProduct = nums[0];
for (int index = 1; index < n; index++) {
long long currentValue = nums[index];
/*
* Preserve both previous states because
* a negative value can swap their roles.
*/
long long previousMax = currentMax;
long long previousMin = currentMin;
/*
* Either start fresh or extend one of
* the previous product subarrays.
*/
currentMax = max({
currentValue,
previousMax * currentValue,
previousMin * currentValue
});
currentMin = min({
currentValue,
previousMax * currentValue,
previousMin * currentValue
});
// Record the best product found anywhere so far.
if (currentMax > maxProduct) {
maxProduct = currentMax;
}
}
return maxProduct;
}
};
int main() {
vector<int> nums = {2, 3, -2, 4};
Solution solution;
cout << solution.maxProduct(nums) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the array size. Every element is processed once using a constant number of comparisons and multiplications.

Space Complexity: O(1), because only currentMax, currentMin, previousMax, previousMin, and maxProduct require auxiliary storage.

FAQs

Q1. Why must both currentMax and currentMin be tracked?

Multiplication by a negative number reverses the order of products. The smallest negative product can become the largest positive product after another negative value appears.

Q2. Why must the previous maximum and minimum be stored before updating either value?

The new currentMax and currentMin must both use the states from the previous index. Updating one value first could incorrectly make the second calculation use a mixture of old and new states.

Q3. How does the Optimal Approach handle zero?

The current element itself is always considered as a candidate. At a zero, both current products can become zero. A later non-zero value can then start a fresh subarray without requiring separate reset logic.

Q4. Why does the Optimal Approach consider starting a new subarray at every position?

The previous product may be zero or may make the current result worse. Treating the current element alone as a candidate allows an unhelpful earlier product to be discarded.

Q5. How can the actual maximum-product subarray be returned?

Track the starting position associated with currentMax and currentMin. Whenever a fresh subarray is selected, reset the corresponding start. Whenever maxProduct improves, store the current maximum range.

Arrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

72.4k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cell...

79.8k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the t...

110.4k
Comments0