Start learning free

LESSON 451 OF 540 · DYNAMIC PROGRAMMING

Maximum Product Subarray in Go: One Pass with Max and Min

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 <= len(nums) <= 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 9
    Ctrl + Enter to check

    GO · DYNAMIC PROGRAMMING

    Maximum Product Subarray in Go, explained

    Problem overview

    The function maxProduct receives a slice nums of integers and returns the largest product of a subarray: a run of one or more elements that stand next to each other. The product is all the elements of the run multiplied together.

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

    Approach: track the best and the worst product ending here

    Trying every subarray takes O(n²) time, and the statement asks for O(n) time and O(1) extra space. The solution makes one pass and keeps, for the current element, two numbers:

    • maxHere: the largest product of a subarray that ends at the current element;
    • minHere: the smallest product of a subarray that ends at the current element.

    The smallest product matters because of negative numbers. Multiplying by a negative number flips the order: the most negative product becomes the largest. A subarray with a very negative product can turn into the winner when the next element is negative.

    At each element x = nums[i], a subarray ending there either starts fresh at x or extends one that ends at the previous element. Starting fresh is how a product recovers after a 0, since a 0 turns every longer product into 0. So the new maxHere is the larger of x and maxHere * x, and the new minHere is the smaller of x and minHere * x. When x is negative, the roles of the two old values swap first: the old minimum times a negative number gives the new maximum candidate. The best answer so far, result, is the largest maxHere seen.

    The trace for [-2, 3, -4] shows the flip. The values after each element are:

    start       maxHere -2   minHere -2   result -2
i=1, x=3    maxHere 3    minHere -6   result 3
i=2, x=-4   maxHere 24   minHere -12  result 24

    At the last element, the old minHere of -6 times -4 gives the 24.

    Step by step

    1. Create maxHere := nums[0]. At the first element, the only subarray ending there is the element itself.
    2. Create minHere := nums[0] the same way.
    3. Create result := nums[0]: the largest product found so far. A subarray needs at least one element, so the first element alone is a valid start, even when it is negative.
    4. Loop over the rest with for i := 1; i < len(nums); i++. Element 0 is already counted.
    5. Swap on a negative. If nums[i] < 0, run maxHere, minHere = minHere, maxHere. After the swap, each variable is the right one to multiply by nums[i].
    6. Update maxHere to max(nums[i], maxHere*nums[i]): start fresh or extend.
    7. Update minHere to min(nums[i], minHere*nums[i]), the same two choices, keeping the smallest.
    8. Update result to max(result, maxHere). The best subarray ends at some element, so looking at the best one ending at each element finds it.
    9. Return result after the loop.

    The solution in Go

    func maxProduct(nums []int) int {
    maxHere := nums[0]
    minHere := nums[0]
    result := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] < 0 {
            maxHere, minHere = minHere, maxHere
        }
        maxHere = max(nums[i], maxHere*nums[i])
        minHere = min(nums[i], minHere*nums[i])
        result = max(result, maxHere)
    }
    return result
}

    The Go details worth knowing:

    • Tuple assignment. maxHere, minHere = minHere, maxHere evaluates both right-hand values before it assigns either, so the two variables swap without a third one. Writing the swap as two separate statements, maxHere = minHere and then minHere = maxHere, would leave both variables equal to the old minHere.
    • Built-in max and min. Since Go 1.21 these are built-in functions for ordered types, so no import or helper is needed.
    • Order of the updates. minHere is updated after maxHere, and its formula uses only minHere and nums[i], not the new maxHere. Both formulas use the values after the swap, so the order between these two lines does not matter.
    • Integer size. int is 64 bits in Go, and the statement promises that every subarray product fits in 32 bits. The intermediate products maxHere*nums[i] are products of a subarray too, so they never overflow.
    • Empty slices. nums[0] panics on an empty slice. The lesson's constraints guarantee at least one element.

    Complexity

    Time: O(n). The loop makes one pass, and each round does a constant amount of work: one comparison, one swap and a few multiplications.

    Space: O(1). The function uses three integers, whatever the length of nums.

    Edge cases and common mistakes

    • A single negative element. [-3] returns -3, not 0. That is why result starts at nums[0] and not at 0.
    • A zero splits the problem. [-2, 0, -1] returns 0. At the 0, both totals become 0, and the next element starts a fresh run.
    • Two negatives. [-2, -3, -4] returns 12, from the last two elements. [-1, -1] returns 1.
    • A negative in the middle. [3, -1, 4] returns 4: the negative element is better left out. [2, -5, -2, -4, 3] returns 24.
    • Keeping only the maximum. Tracking just maxHere fails on [-2, 3, -4], where the winner comes from a negative product that the next negative turns around.
    • Forgetting the fresh start. Without nums[i] as an option in max, a 0 would force every later product to stay 0.
    • Skipping the swap. With a negative nums[i], multiplying maxHere by it would give a small number, and the real maximum candidate, minHere * nums[i], would never be tried.
    • Starting result at 0. It returns a wrong answer whenever every element is negative.

    Testing

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