{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Maximum Product Subarray – Solution & Complexity

Interview solutions
/
Maximum Product Subarray

Solution Walkthrough

  1. Step 1: Understand why sign changes matter

    • Products behave differently from sums because multiplying by a negative flips the sign.
    • A very small negative running product can become the best positive answer after another negative value.

  2. Step 2: Brute-force every starting point

    • Start each subarray at every index and keep multiplying as you extend the right edge.
    • This checks all O(n^2) contiguous subarrays and is correct, but too slow for long inputs.
    def maximum_product_subarray(nums):
    best = nums[0]
    for start in range(len(nums)):
        product = 1
        for end in range(start, len(nums)):
            product *= nums[end]
            best = max(best, product)
    return best

  3. Step 3: Keep both extremes at each position

    • Let max_ending be the largest product ending at the current index.
    • Let min_ending be the smallest product ending there, because a future negative number may flip it into the new maximum.

  4. Step 4: Update the running max and min in one pass

    • When the current number is negative, swap the running extremes before multiplying.
    • Then decide whether to start fresh at num or extend the previous product.
    def maximum_product_subarray(nums):
    max_ending = nums[0]
    min_ending = nums[0]
    best = nums[0]
    for num in nums[1:]:
        if num < 0:
            max_ending, min_ending = min_ending, max_ending
        max_ending = max(num, max_ending * num)
        min_ending = min(num, min_ending * num)
        best = max(best, max_ending)
    return best

  5. Step 5: Dry run / state trace

    Trace nums = [2, 3, -2, 4].

    nummax_ending beforemin_ending beforemax_ending aftermin_ending afterbest
    222222
    322636
    -263-2-126
    4-2-124-486

    The negative -2 destroys the running maximum but creates a much smaller negative product, which is exactly why the minimum track is necessary.

  6. Step 6: Final solution and complexity

    Track the largest and smallest products ending at each index; one pass gives O(n) time and O(1) space.

    def maximum_product_subarray(nums: list[int]) -> int:
    max_ending = nums[0]
    min_ending = nums[0]
    best = nums[0]
    for num in nums[1:]:
        if num < 0:
            max_ending, min_ending = min_ending, max_ending
        max_ending = max(num, max_ending * num)
        min_ending = min(num, min_ending * num)
        best = max(best, max_ending)
    return best

FAQ

See also

Practice Maximum Product Subarray online (run code in the browser)Best Time to Buy and Sell Stock solution (easy)Coin Change solution (medium)House Robber solution (medium)House Robber II solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?