Find Maximum Product Subarray

Title: Find Maximum Product Subarray

In this guide, you’ll learn how to solve the Find Maximum Product Subarray problem in Java: given an integer array that may contain negative numbers and zeros, find the contiguous subarray with the largest product and return that product.

This problem looks like a simple variation of the maximum subarray sum problem, but multiplication introduces a twist: two negative numbers multiply to a positive number, so the smallest (most negative) running product can suddenly become the largest once it meets another negative value. You’ll see how to track both a running maximum and a running minimum to handle this correctly in a single pass.

Understanding the Problem

Given an array of integers nums, you need to find a contiguous subarray (at least one element) whose product of all its elements is the largest possible, then return that product. A subarray must use consecutive elements; you cannot skip elements to improve the product.

The presence of negative numbers makes this harder than the sum version. A single negative number flips the sign of everything multiplied with it, so the subarray that currently has the smallest (most negative) product can become the best candidate the moment you multiply it by another negative number. Zeros are easier: any subarray product that includes a zero collapses to zero, so a zero acts as a natural reset point.

Approach to Solve the Problem

1. Check that nums is not null and not empty; if it is, throw an IllegalArgumentException or handle the case according to your contract.
2. Initialize maxSoFar, maxEndingHere, and minEndingHere to nums[0] so the first element is always a valid candidate.
3. Loop through the array starting at index 1.
4. For the current element, check if it is negative. If it is, swap maxEndingHere and minEndingHere before updating them, because multiplying by a negative number turns the smaller running product into the larger one.
5. Update maxEndingHere to the larger of the current element alone and the current element multiplied by the (possibly swapped) maxEndingHere.
6. Update minEndingHere to the smaller of the current element alone and the current element multiplied by the (possibly swapped) minEndingHere.
7. Update maxSoFar to the larger of itself and the new maxEndingHere.
8. After the loop completes, return maxSoFar as the answer.

Java Program

public class MaxProductSubarray {

    public static int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Input array must not be empty");
        }

        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        int minEndingHere = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int current = nums[i];

            if (current < 0) {
                int temp = maxEndingHere;
                maxEndingHere = minEndingHere;
                minEndingHere = temp;
            }

            maxEndingHere = Math.max(current, maxEndingHere * current);
            minEndingHere = Math.min(current, minEndingHere * current);

            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, -2, 4};
        System.out.println("Maximum product subarray: " + maxProduct(nums));
    }
}

Explanation of the Program

• maxProduct first validates the input, then initializes all three trackers to nums[0] so a single-element array returns the correct result immediately.
• Inside the loop, the swap of maxEndingHere and minEndingHere happens only when current is negative, which is what lets a very negative running product become the new maximum on the next multiplication.
• Math.max and Math.min compare the current element on its own against the current element multiplied by the running tracker, so a subarray can restart at the current element whenever that produces a better result than extending the previous one.
• maxSoFar is updated once per iteration with the best maxEndingHere seen so far, which is the value the method ultimately returns.
• The method runs in a single pass, so it never looks back at earlier elements once it has folded their effect into maxEndingHere and minEndingHere.

Step-by-Step Trace

Here’s a dry run for nums = [2, -5, -2, -4, 3], which should produce a maximum product of 24 (from the subarray [-2, -4, 3]).

At the end of each iteration, maxEndingHere holds the maximum product of any subarray that ends exactly at the current index, and maxSoFar holds the best value seen across every index examined so far.

Examples

Example 1: Array with a Single Negative Number

With nums = {2, 3, -2, 4}, the best subarray is [2, 3], which multiplies to 6. Extending further to include -2 or 4 only lowers the product.

int[] nums = {2, 3, -2, 4};
System.out.println(maxProduct(nums));
// Output: 6 (from the subarray [2, 3])

Example 2: Array Containing a Zero

With nums = {-2, 0, -1}, every subarray that spans the zero collapses to 0, and no subarray avoiding the zero does better, so the answer is 0.

int[] nums = {-2, 0, -1};
System.out.println(maxProduct(nums));
// Output: 0 (from the subarray [0])

Common Mistakes to Avoid

These are the mistakes that most often trip up candidates solving this problem for the first time.

• Tracking only a running maximum – fails on arrays with negative numbers because the best answer can come from multiplying two negative products together. Track a running minEndingHere alongside maxEndingHere.
• Updating before swapping – recomputing maxEndingHere and minEndingHere before swapping them on a negative element uses the wrong previous extreme in the multiplication. Swap the two variables first, then recompute both from the swapped values.
• Initializing maxSoFar to 0 – returns the wrong answer of 0 for arrays where every possible subarray product is negative. Initialize maxSoFar, maxEndingHere, and minEndingHere to nums[0] instead.
• Adding special-case logic for zeros – is unnecessary and error-prone, since multiplying through a zero already drives both maxEndingHere and minEndingHere to zero on its own. Let the existing recurrence handle zeros; do not add a manual reset.

Edge Cases to Test

Walk through these input shapes out loud before you call the solution finished.

• Empty array
• Single-element array
• Array containing a zero
• All negative elements with an odd count
• All negative elements with an even count
• All zeros
• Maximum product spanning the entire array

Additional Considerations

The algorithm makes a single pass over the array, so the time complexity is O(n). It only keeps three integer trackers regardless of input size, so the space complexity is O(1) beyond the input array itself.

Because products grow much faster than sums, long arrays of large numbers can overflow a Java int. If the problem allows large magnitudes, widen maxEndingHere, minEndingHere, and maxSoFar to long to delay overflow, and document the remaining limit.

This method is a direct extension of Kadane’s algorithm for maximum subarray sum. The sum version only needs one running tracker because adding a negative number never flips which running total is larger; the product version needs two trackers because multiplying by a negative number can flip exactly that.

Interview Follow-up Questions

An interviewer rarely stops at the base problem. Expect at least one of these.

• What if you also need the subarray itself, not just the product? – track the start and end indices alongside maxEndingHere and update them whenever maxEndingHere changes.
• What if the array contains floating-point numbers? – the same swap logic applies; just be aware that values extremely close to zero can introduce precision noise when compared for equality.
• What if you need the maximum product of a subsequence instead of a subarray? – dropping the contiguity requirement turns this into counting negative values and multiplying all nonzero elements together, which is a different algorithm entirely.
• What if the array arrives as a stream and you cannot revisit earlier elements? – keep only maxEndingHere, minEndingHere, and maxSoFar updated per element as it arrives; the recurrence is already online and needs no buffering.
• What if you must solve it with read-only input and no extra array allocation? – the three-tracker version already uses only O(1) extra space, so the constraint is already satisfied without any change.

Conclusion

Finding the maximum product subarray comes down to tracking both the best and worst running product at every index, because a negative number can turn the worst case into the best one with a single multiplication. Once you internalize that swap step, the rest of the algorithm is a straightforward single pass.

Try adapting maxProduct to return the subarray boundaries, or to work over a long[] input, to make sure you understand why each tracker is needed. You can learn more about array-based problems in the Arrays category on dailyjavaconcept.com.