Maximum Subarray Product — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Maximum Subarray Product problem optimally.
O(n)O(1)Problem Description
Given an integer array nums, find the contiguous subarray (containing at least one element) whose elements multiply to the largest possible value. Return that maximum product as a 32‑bit signed integer. The subarray must consist of consecutive positions; you may not reorder or skip elements. The algorithm should run in linear time and use O(1) extra space beyond the input.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Subarray Product"
WHY DOES IT MATTER?
The pattern of maintaining both maximum and minimum state captures the dual nature of multiplication with sign changes, a technique that recurs in problems where an operation is not monotonic, such as stock‑price profit with transaction fees or longest subarray with bounded product.
OPTIMIZATION CHALLENGE
Recognizing that the minimum product can become the maximum after a single negative multiplication reduces the problem from quadratic enumeration to a constant‑space, single‑pass update, eliminating the need for nested loops or extra arrays.
REAL-WORLD CONNECTION
Think of a financial portfolio that can hold both assets and liabilities; a loss (negative) today can become a gain when paired with a later loss, similar to hedging strategies where two losing positions offset each other to produce profit.
During an interview, compute maxEndingHere and minEndingHere simultaneously, swap them when you encounter a negative, and always compare against a global max – this one‑liner update is both concise and hard to mess up.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The maximum product subarray problem cannot be solved by a simple greedy scan that only tracks the maximum because multiplication introduces sign changes: a negative number can turn a small minimum into a large maximum when another negative appears later. A naive O(n^2) approach enumerates every subarray and multiplies its elements, which quickly overflows time limits and suffers from integer overflow on large inputs. The optimal paradigm uses dynamic programming with two running values – the maximum product ending at the current index and the minimum product ending at the current index – because the minimum can become the maximum after multiplying by a negative. By updating these two values in a single pass, we capture the effect of sign flips while maintaining O(1) extra space, delivering a linear‑time solution suitable for the 32‑bit signed integer constraint.
Interview Questions on This Problem
Q1How does the presence of zeros affect the maximum product subarray algorithm and how do you handle them?
A zero resets any ongoing product because any subarray containing it has product zero. In the linear scan, when nums[i]==0 we set both maxEndingHere and minEndingHere to 1 (or 0) and update the global answer with max(answer,0), effectively starting a new subarray after the zero.
Q2Can you modify the algorithm to also return the indices of the subarray that yields the maximum product?
Yes. Track start indices for the current max and min products; when you reset due to a negative swap or a zero, update the candidate start. Whenever globalMax is updated, store the current start and i as the best range.
Q3Why is it unsafe to use a single variable for the running product when the array contains negative numbers?
A single variable loses information about the smallest (most negative) product seen so far. Multiplying a future negative number with that smallest value could produce the largest positive product, so discarding it leads to incorrect results, especially in sequences like [-2, -3, 4].
Examples
Input
[2,3,-2,4]
Output
6
Explanation: Start with the first element: product=2 (max=2, min=2). Extend to second element 3 → new max=2*3=6, new min=2*3=6. Current best=6. Third element -2 flips sign: max becomes min*-2 = -12, min becomes max*-2 = -12, but we also consider -2 alone, so max=-2, min=-12. Best stays 6. Fourth element 4 → max = max(4, -2*4, -12*4)=max(4,-8,-48)=4, min = min(4,-8,-48)=-48. Best remains 6. The subarray [2,3] yields product 6, which is maximal.
Input
[-2,0,-1]
Output
0
Explanation: Initialize with -2 → max=-2, min=-2, best=-2. Next element 0 resets both max and min to 0 (or 0 alone), updating best to 0. Last element -1: max = max(-1,0*-1)=0, min = min(-1,0*-1)=-1, best stays 0. The subarray [0] gives product 0, the highest achievable.
Input
[-2,-3,-2,-40]
Output
480
Explanation: First element -2 → max=-2, min=-2, best=-2. Second -3 flips signs: max = max(-3, -2*-3)=6, min = min(-3, -2*-3)=-3, best=6 (subarray [-2,-3]). Third -2 again flips: max = max(-2, 6*-2) = max(-2,-12) = -2, min = min(-2, -3*-2)=min(-2,6)= -2, best remains 6. Fourth -40 flips: max = max(-40, -2*-40)=80, min = min(-40, -2*-40) = -40, best updates to 80 (subarray [-2,-40]). However, considering the product of the first three numbers: -2 * -3 * -2 = -12, not larger. The maximal product is obtained from subarray [-2,-40] with product 80. (Correction: the true maximal product is 480 from subarray [-2,-3,-2,-40] = (-2)*(-3)*(-2)*(-40)=480, which exceeds 80. The algorithm tracks both max and min, eventually yielding max=480 at the last step, so the answer is 480.)
Input
[1,-2,-3,0,7,-8,2]
Output
112
Explanation: Processing yields a maximum product of 112 from subarray [-8,2] after the zero resets the running products. The algorithm maintains running max/min and updates the global best accordingly.
Constraints
- 1 <= nums.length <= 100000
- -1000000000 <= nums[i] <= 1000000000
- Result fits in a signed 32‑bit integer
- Array contains at least one element
Optimal Approach & Strategy
Maintain maxEndingHere and minEndingHere while scanning once; update them based on the current number and track the global maximum, achieving O(n) time and O(1) space.
Brute Force Approach
Enumerate every possible subarray, multiply its elements, and keep the largest product; this costs O(n^2) time and risks overflow.
Code Solutions
function maxProduct(nums){
let maxProd = nums[0];
let minProd = nums[0];
let ans = nums[0];
for(let i=1;i<nums.length;i++){
const cur = nums[i];
if(cur<0){
const tmp = maxProd;
maxProd = minProd;
minProd = tmp;
}
maxProd = Math.max(cur, maxProd*cur);
minProd = Math.min(cur, minProd*cur);
ans = Math.max(ans, maxProd);
}
return ans|0; // cast to 32‑bit int
}
const fs = require('fs');
function main(){
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
const n = data[0];
const nums = data.slice(1,1+n);
console.log(maxProduct(nums));
}
main();#include <bits/stdc++.h>
using namespace std;
int maxProduct(const vector<int>& nums) {
long long maxProd = nums[0];
long long minProd = nums[0];
long long ans = nums[0];
for(size_t i=1;i<nums.size();++i){
long long cur = nums[i];
if(cur<0) swap(maxProd, minProd);
maxProd = max(cur, maxProd*cur);
minProd = min(cur, minProd*cur);
ans = max(ans, maxProd);
}
return static_cast<int>(ans);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> nums(n);
for(int i=0;i<n;++i) cin>>nums[i];
cout<<maxProduct(nums);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static int maxProduct(int[] nums) {
long maxProd = nums[0];
long minProd = nums[0];
long ans = nums[0];
for(int i=1;i<nums.length;i++){
long cur = nums[i];
if(cur<0){
long tmp = maxProd;
maxProd = minProd;
minProd = tmp;
}
maxProd = Math.max(cur, maxProd*cur);
minProd = Math.min(cur, minProd*cur);
ans = Math.max(ans, maxProd);
}
return (int)ans;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line==null||line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
int[] nums = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) nums[i]=Integer.parseInt(st.nextToken());
System.out.println(maxProduct(nums));
}
}def maxProduct(nums):
max_prod = min_prod = ans = nums[0]
for cur in nums[1:]:
if cur < 0:
max_prod, min_prod = min_prod, max_prod
max_prod = max(cur, max_prod * cur)
min_prod = min(cur, min_prod * cur)
ans = max(ans, max_prod)
return int(ans)
if __name__ == "__main__":
import sys
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
sys.exit()
n = data[0]
nums = data[1:1+n]
print(maxProduct(nums))function maxProduct(nums){
let maxProd = nums[0];
let minProd = nums[0];
let ans = nums[0];
for(let i=1;i<nums.length;i++){
const cur = nums[i];
if(cur<0){
const tmp = maxProd;
maxProd = minProd;
minProd = tmp;
}
maxProd = Math.max(cur, maxProd*cur);
minProd = Math.min(cur, minProd*cur);
ans = Math.max(ans, maxProd);
}
return ans|0; // cast to 32‑bit int
}
const fs = require('fs');
function main(){
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
const n = data[0];
const nums = data.slice(1,1+n);
console.log(maxProduct(nums));
}
main();Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.