Problem Statement:
Given an integer array nums, find a subarray that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10- The product of any subarray of
numsis guaranteed to fit in a 32-bit integer.
Approach:
- Start with the first element as:
-
maxProdSoFar→ maximum product ending at current index. minProdSoFar→ minimum product ending at current index (important because multiplying with a negative can flip it).totalMax→ overall maximum product.
-
- Iterate through the array:
- For each element arr[i] (from index 1 to end):
- Store the
previous maxProdSoFarin a temporary variable (maxProdSoFarCopy). - Update maxProdSoFar as the maximum among:
- Current element alone
(arr[i]) - Product of current element with previous max product
(maxProdSoFar * arr[i]) - Product of current element with previous min product
(minProdSoFar * arr[i]) - Update
minProdSoFaras the minimum among the same three values. - Update totalMax as the maximum between current
totalMaxandmaxProdSoFar.
- Current element alone
- Store the
- For each element arr[i] (from index 1 to end):
- After traversing the whole array, totalMax holds the
maximum product of any subarray.
Time & Space Complexity:
Time Complexity: O(n)
Space Complexity: O(1)
Dry Run
Input: arr = [2, 3, -2, 4]
Step 0: Start Function maxProduct([2, 3, -2, 4])
Initialize:
maxProdSoFar = minProdSoFar = totalMax = arr[0] = 2
Iteration i = 1, arr[1] = 3
- maxProdSoFarCopy = maxProdSoFar = 2
- maxProdSoFar = Math.max( arr[1], maxProdSoFar * arr[1], minProdSoFar * arr[1] )
= Math.max( 3, 2 * 3 = 6, 2 * 3 = 6 ) = 6
- minProdSoFar = Math.min( arr[1], maxProdSoFarCopy * arr[1], minProdSoFar * arr[1] )
= Math.min( 3, 2 * 3 = 6, 2 * 3 = 6 ) = 3
- totalMax = Math.max(totalMax, maxProdSoFar) = Math.max(2, 6) = 6
State after i=1:
maxProdSoFar = 6, minProdSoFar = 3, totalMax = 6
Iteration i = 2, arr[2] = -2
- maxProdSoFarCopy = maxProdSoFar = 6
- maxProdSoFar = Math.max( -2, 6 * (-2) = -12, 3 * (-2) = -6 ) = -2
- minProdSoFar = Math.min( -2, 6 * (-2) = -12, 3 * (-2) = -6 ) = -12
- totalMax = Math.max(6, -2) = 6
State after i=2:
maxProdSoFar = -2, minProdSoFar = -12, totalMax = 6
Iteration i = 3, arr[3] = 4
- maxProdSoFarCopy = maxProdSoFar = -2
- maxProdSoFar = Math.max( 4, -2 * 4 = -8, -12 * 4 = -48 ) = 4
- minProdSoFar = Math.min( 4, -2 * 4 = -8, -12 * 4 = -48 ) = -48
- totalMax = Math.max(6, 4) = 6
State after i=3:
maxProdSoFar = 4, minProdSoFar = -48, totalMax = 6
Step 3: End
Return totalMax = 6
Output: 6 (Maximum product subarray is [2,3] → 6)
Visualisation:
var maxProduct = function(arr) {
if (!arr || arr.length === 0) return 0; // defensive
let maxProdSoFar = arr[0];
let minProdSoFar = arr[0];
let totalMax = arr[0];
for (let i = 1; i < arr.length; i++) {
const current = arr[i];
const prevMax = maxProdSoFar;
maxProdSoFar = Math.max(current, prevMax * current, minProdSoFar * current);
minProdSoFar = Math.min(current, prevMax * current, minProdSoFar * current);
totalMax = Math.max(totalMax, maxProdSoFar);
}
return totalMax;
};
def max_product(arr):
if not arr:
return 0 # defensive
max_prod_so_far = arr[0]
min_prod_so_far = arr[0]
total_max = arr[0]
for i in range(1, len(arr)):
current = arr[i]
prev_max = max_prod_so_far
max_prod_so_far = max(current, prev_max * current, min_prod_so_far * current)
min_prod_so_far = min(current, prev_max * current, min_prod_so_far * current)
total_max = max(total_max, max_prod_so_far)
return total_max
public class Solution {
public static int maxProduct(int[] arr) {
if (arr == null || arr.length == 0) return 0; // defensive
int maxProdSoFar = arr[0];
int minProdSoFar = arr[0];
int totalMax = arr[0];
for (int i = 1; i < arr.length; i++) {
int current = arr[i];
int prevMax = maxProdSoFar;
maxProdSoFar = Math.max(current, Math.max(prevMax * current, minProdSoFar * current));
minProdSoFar = Math.min(current, Math.min(prevMax * current, minProdSoFar * current));
totalMax = Math.max(totalMax, maxProdSoFar);
}
return totalMax;
}
}
#include <vector>
#include <algorithm>
int maxProduct(const std::vector& arr) {
if (arr.empty()) return 0; // defensive
int maxProdSoFar = arr[0];
int minProdSoFar = arr[0];
int totalMax = arr[0];
for (size_t i = 1; i < arr.size(); ++i) {
int current = arr[i];
int prevMax = maxProdSoFar;
maxProdSoFar = std::max(current, std::max(prevMax * current, minProdSoFar * current));
minProdSoFar = std::min(current, std::min(prevMax * current, minProdSoFar * current));
totalMax = std::max(totalMax, maxProdSoFar);
}
return totalMax;
}
#include <limits.h>
int maxProduct(int arr[], int n) {
if (n <= 0) return 0; // defensive
int maxProdSoFar = arr[0];
int minProdSoFar = arr[0];
int totalMax = arr[0];
for (int i = 1; i < n; ++i) {
int current = arr[i];
int prevMax = maxProdSoFar;
int candidate1 = current;
int candidate2 = prevMax * current;
int candidate3 = minProdSoFar * current;
// compute max of three
int newMax = candidate1;
if (candidate2 > newMax) newMax = candidate2;
if (candidate3 > newMax) newMax = candidate3;
// compute min of three
int newMin = candidate1;
if (candidate2 < newMin) newMin = candidate2;
if (candidate3 < newMin) newMin = candidate3;
maxProdSoFar = newMax;
minProdSoFar = newMin;
if (maxProdSoFar > totalMax) totalMax = maxProdSoFar;
}
return totalMax;
}
using System;
public class Solution {
public static int MaxProduct(int[] arr) {
if (arr == null || arr.Length == 0) return 0; // defensive
int maxProdSoFar = arr[0];
int minProdSoFar = arr[0];
int totalMax = arr[0];
for (int i = 1; i < arr.Length; i++) {
int current = arr[i];
int prevMax = maxProdSoFar;
maxProdSoFar = Math.Max(current, Math.Max(prevMax * current, minProdSoFar * current));
minProdSoFar = Math.Min(current, Math.Min(prevMax * current, minProdSoFar * current));
totalMax = Math.Max(totalMax, maxProdSoFar);
}
return totalMax;
}
}
