← Recursion & DP

Micro-Drill #168 — Maximum Product Subarray

Recursion & DP Target: 10s

Track both max and min product (negative * negative = positive). Swap on negative number.

def maxProduct(nums):
    res = mx = mn = nums[0]
    for x in nums[1:]:
        if x < 0:
            mx, mn = mn, mx  # swap before multiply
        mx = max(x, mx * x)
        mn = min(x, mn * x)
        res = max(res, mx)
    return res

Type it from memory. Go.

Practice Problems

• 152. Maximum Product Subarray
• 628. Maximum Product of Three Numbers

Related Coding Drills

• Drill #3 — Max subarray sum (Kadane's) Medium
• Drill #133 — Product of Array Except Self Medium