Find Maximum Product Subarray in Java
Problem
The maximum product subarray is the largest possible product of any contiguous run of elements — a problem complicated by negative numbers, since multiplying two negatives can turn a very small product into the new largest one.
Given an array of integers, find the largest product achievable by any contiguous subarray.
Java Program
public class MaxProductSubarray {
public static void main(String[] args) {
int[] arr = {2, -5, 3, -2, 4, -3};
long maxProduct = arr[0];
for (int i = 0; i < arr.length; i++) {
long product = 1; // reset for each new starting index
for (int j = i; j < arr.length; j++) {
product *= arr[j]; // extend the subarray by one element
if (product > maxProduct) maxProduct = product;
}
}
System.out.println("Maximum product subarray: " + maxProduct);
}
}Output
Core Logic
Computing the product of every possible contiguous subarray directly, and keeping track of the largest one seen, checks every candidate explicitly.
- 1The outer loop picks a starting index
ifor a candidate subarray. - 2The inner loop extends the subarray one element at a time, multiplying a running
productbyarr[j]. - 3After each extension,
productis compared againstmaxProduct, updating it whenever a larger value is found. - 4By the time both loops finish, every one of the array's contiguous subarrays has had its product checked.
[2, -5, 3, -2, 4, -3], the subarray [2, -5, 3, -2, 4] has a product of 240, the largest found across every subarray tried — the full array's product is actually -720, since the trailing -3 flips its sign.Key Point: This brute-force scan naturally handles the negative-number complication just by trying every subarray — it's only the single-pass optimized version that needs to think carefully about negatives.
Why: Every possible subarray's product is computed directly by extending the inner loop's running total, so the nested loops do O(n²) work with no extra memory.
Key Concepts
Approach 2: Track Max and Min
public class MaxProductSubarrayOptimized {
public static void main(String[] args) {
int[] arr = {2, -5, 3, -2, 4, -3};
long maxEndingHere = arr[0];
long minEndingHere = arr[0];
long maxSoFar = arr[0];
for (int i = 1; i < arr.length; i++) {
long current = arr[i];
// minEndingHere * current is included since a negative current can flip a very negative product into the new max
long candidateMax = Math.max(current, Math.max(maxEndingHere * current, minEndingHere * current));
long candidateMin = Math.min(current, Math.min(maxEndingHere * current, minEndingHere * current));
maxEndingHere = candidateMax;
minEndingHere = candidateMin;
maxSoFar = Math.max(maxSoFar, maxEndingHere); // best maxEndingHere seen anywhere in the scan
}
System.out.println("Maximum product subarray: " + maxSoFar);
}
}
Output
Core Logic
Because multiplying by a negative number can flip the smallest running product into the largest one, tracking both a running maximum AND a running minimum at every step is what makes a single pass work.
- 1
maxEndingHereandminEndingHereboth track the best and worst products of a subarray ending at the current position. - 2At each element, three candidates are compared: the element alone,
maxEndingHere * current, andminEndingHere * current. - 3The largest of the three becomes the new
maxEndingHere, and the smallest becomes the newminEndingHere. - 4
maxSoFartracks the bestmaxEndingHereseen across the whole scan.
-2 in [2, -5, 3, -2, 4, -3], multiplying it by the previous minEndingHere (-30, not the running max of 3) produces 60 — the value that two steps later, once multiplied by 4, becomes the true maximum of 240.Key Point: Tracking only a running maximum — the way the maximum subarray sum problem does — silently gives the wrong answer here, since a very negative running product can become the largest one the moment it's multiplied by another negative number.
Why: Each element is visited once, but both a running maximum AND running minimum have to be tracked, since multiplying by a negative number can flip the smallest running product into the largest one.