Start learning free

LESSON 447 OF 536 · DYNAMIC PROGRAMMING

Maximum Product Subarray in Java: O(n) Time, O(1) Space

Practice O(n) Read the full explanation

Given an array of integers nums, find the subarray with the largest product and return that product.

A subarray is a run of one or more elements that stand next to each other in nums. Its product is all of its elements multiplied together.

Example 1:

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: The subarray [2, 3] has the largest product, 2 × 3 = 6. -2 is the only negative number, so every subarray that includes it has a negative product.

Example 2:

Input: nums = [-2, 0, -1]
Output: 0
Explanation: The answer can't be 2: [-2, -1] is not a subarray, because 0 stands between them. The subarray [0] gives 0, and every other subarray gives 0 or less.

Example 3:

Input: nums = [-2, 3, -4]
Output: 24
Explanation: The whole array: the two negative numbers cancel out, -2 × 3 × -4 = 24.

Constraints:

  • 1 <= nums.length <= 105
  • -10 <= nums[i] <= 10
  • The product of any subarray of nums fits in a 32-bit integer.

Note:

Your algorithm should run in O(n) time and use O(1) extra space, where n is the length of nums.

STEP 1 OF 11
    Ctrl + Enter to check

    JAVA · DYNAMIC PROGRAMMING

    Maximum Product Subarray in Java, explained

    Problem overview

    The method maxProduct receives an array of integers nums and returns the largest product of a subarray. A subarray is a run of one or more elements that stand next to each other, and its product is all its elements multiplied together. The lesson promises that every subarray's product fits in a 32-bit int.

    For [2, 3, -2, 4] the answer is 6, from [2, 3]. The only negative number is -2, so any subarray that includes it has a negative product. For [-2, 0, -1] the answer is 0: [-2, -1] is not a subarray because the 0 stands between them. For [-2, 3, -4] the answer is 24, the whole array, where the two negatives cancel out.

    Approach: track the largest and the smallest product ending here

    For maximum sum, a running best that ends at the current element is enough. Products need a second number, because a negative factor flips the order: the most negative product so far, times a negative number, becomes the largest. So the loop keeps two values for subarrays that end at the current element:

    • maxHere, the largest product;
    • minHere, the smallest product, which may be a large negative number.

    At each new element x, the best subarray ending at x either starts fresh at x or extends the best one ending just before it. Starting fresh is how a product recovers after a 0, because multiplying by 0 destroys everything before it. The smallest product follows the same two choices. A third variable, result, remembers the largest maxHere seen anywhere.

    When x is negative, the roles swap: the largest product ending here comes from multiplying x by the old smallest one, and the other way around. The solution swaps maxHere and minHere first, so the same two lines work for every sign.

    The loop makes one pass with a constant amount of work per element and needs only a few variables, so the time is O(n) and the extra space is O(1).

    Step by step

    1. Start maxHere at nums[0]. The only subarray ending at the first element is the element itself.
    2. Start minHere at nums[0] for the same reason. It is kept because a negative number will turn it into the largest.
    3. Start result at nums[0]. A subarray needs at least one element, so the first element alone is a valid answer even when it is negative.
    4. Loop from index 1 to the end, because element 0 is already counted.
    5. Test for a negative element, nums[i] < 0. Multiplying by a negative number flips the order, so inside this if the two values swap.
    6. Save maxHere in temp. Without it the next assignment would overwrite maxHere and lose its value.
    7. Swap: copy minHere into maxHere and temp into minHere. Now each variable holds the right number to multiply by the negative element.
    8. Update maxHere to the larger of nums[i] alone and maxHere * nums[i], with Math.max.
    9. Update minHere to the smaller of nums[i] alone and minHere * nums[i], with Math.min.
    10. Update result to the larger of result and maxHere. The best subarray ends at some element, so checking the best one at every element finds it.
    11. Return result.

    The state after each element, for [2, 3, -2, 4], from a real run of the loop:

    start max=2 min=2 result=2
i=1 nums[i]=3 max=6 min=3 result=6
i=2 nums[i]=-2 max=-2 min=-12 result=6
i=3 nums[i]=4 max=4 min=-48 result=6

    At i = 2, the swap makes maxHere 3 and minHere 6. Multiplying by -2 gives -6 and -12, but maxHere takes the larger of -2 alone and -6, so it becomes -2. At i = 3, the number 4 alone beats -2 times 4, so the product starts fresh. The answer 6 was set at i = 1. For [-2, 3, -4] the run is

    start max=-2 min=-2 result=-2
i=1 nums[i]=3 max=3 min=-6 result=3
i=2 nums[i]=-4 max=24 min=-12 result=24

    where the smallest product -6 becomes the largest, 24, once the second negative arrives.

    The solution in Java

    class Solution {
    public int maxProduct(int[] nums) {
        int maxHere = nums[0];
        int minHere = nums[0];
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = maxHere;
                maxHere = minHere;
                minHere = temp;
            }
            maxHere = Math.max(nums[i], maxHere * nums[i]);
            minHere = Math.min(nums[i], minHere * nums[i]);
            result = Math.max(result, maxHere);
        }
        return result;
    }
}

    Java details worth a closer look:

    • Swapping needs a temporary. Java has no tuple assignment, so temp holds one value while the other is copied over. The variable is declared inside the if block, so it exists only there.
    • Math.max and Math.min take two ints and return an int. The two update lines each read only their own variable, so their order doesn't matter.
    • int overflow. The product of two ints wraps silently if it doesn't fit: 2147483647 * 2 is -2. The lesson guarantees that every subarray's product fits, so the running values stay in range here. In general code, use long or check the bounds.
    • Zero resets the run. When nums[i] is 0, both maxHere and minHere become 0. For the next element x, the choice "x alone" then competes with 0, so the product starts fresh from x where that helps.

    Complexity

    Time: O(n). One pass over the array, with a constant number of operations per element.

    Space: O(1). The code uses maxHere, minHere, result, the loop counter and temp.

    Edge cases and common mistakes

    • A single element. [-3] returns -3 and [0] returns 0. The loop doesn't run, and result keeps the first element. Starting result at 0 would give the wrong answer for [-3].
    • Zeros split the array. [-2, 0, -1] returns 0. The product restarts after the 0, so the two negatives never combine.
    • An odd number of negatives. [-2, -3, -4] returns 12: the best subarray is [-3, -4], leaving the first negative out. Keeping only maxHere can't find that, because the -2 hides inside it.
    • Negatives on both sides of positives. [2, -5, -2, -4, 3] returns 24, from [-2, -4, 3].
    • All positives. [1, 2, 3] returns 6, the product of the whole array.
    • Forgetting to swap before updating. Without the swap, a negative element multiplies the wrong running value, and [-2, 3, -4] would not give 24.
    • Mixing up the two variables. Each update must multiply its own variable. Writing minHere = Math.min(nums[i], maxHere * nums[i]) multiplies the wrong running product and gives wrong answers.

    Testing

    • [2, 3, -2, 4] gives 6.
    • [-2, 0, -1] gives 0.
    • [-2, 3, -4] gives 24.
    • [-3] gives -3.
    • [0] gives 0.
    • [-2, -3, -4] gives 12.
    • [2, -5, -2, -4, 3] gives 24.
    • [1, 2, 3] gives 6.
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free