Finding the maximum product subarray is a classic Medium-level DSA problem that looks simple at first — but quickly becomes tricky due to negative numbers and zeros.

In this article, we'll solve it using two popular approaches:

  1. Prefix & Suffix Scan
  2. Dynamic Programming (Max–Min Tracking)

All examples and implementations are written in Swift.

🧠 Problem Statement

Given an integer array nums, find the contiguous subarray that has the largest product, and return that product.

Example

Input:  [2, 3, -2, 4]
Output: 6

The subarray [2, 3] gives the maximum product.

🚩 Why this problem is tricky

Unlike sum-based problems:

  • Negative numbers can flip results
  • Zero breaks the product chain
  • Two negatives can create a large positive product

Because of this, a simple running product doesn't work reliably.

✅ Approach 1: Prefix & Suffix Scan

Key Idea

The maximum product subarray:

  • May start after a 0
  • May end before a 0
  • May depend on skipping a negative from either side

To cover all cases:

  • Scan left → right using a prefix product
  • Scan right → left using a suffix product

At every step, update the global maximum.

Swift Implementation (Prefix & Suffix)

/// Based on prefix and suffix product
func maxProduct(_ nums: [Int]) -> Int {
    var prefixMax = 1
    var suffixMax = 1
    var result = Int.min
    let n = nums.count
    for (index, value) in nums.enumerated() {
        // Reset when product becomes zero
        if prefixMax == 0 {
            prefixMax = 1
        }
        if suffixMax == 0 {
            suffixMax = 1
        }
        // Multiply from both ends
        prefixMax *= value
        suffixMax *= nums[n - index - 1]
        // Update result
        if prefixMax > result {
            result = prefixMax
        }
        if suffixMax > result {
            result = suffixMax
        }
    }
    return result
}

🧪 Dry Run

Input:

[2, 3, -2, 4]

✔ Final Answer: 6

⏱ Complexity

  • Time: O(n)
  • Space: O(1)

✅ Approach 2: Dynamic Programming (Max–Min Tracking)

Key Insight

At every index:

  • Track the maximum product ending here
  • Track the minimum product ending here

Why?

  • A negative number can turn the smallest product into the largest one.

Swift Implementation (DP Approach)

/// Based on Dynamic Programming
func maxProductII(_ nums: [Int]) -> Int {
    var maxProduct = nums[0]
    var minProduct = nums[0]
    var result = nums[0]
    for index in 1..<nums.count {
        let current = nums[index]
        // Swap when negative flips sign
        if current < 0 {
            swap(&maxProduct, &minProduct)
        }
        maxProduct = max(current, current * maxProduct)
        minProduct = min(current, current * minProduct)
        result = max(result, maxProduct)
    }
    return result
}

Why this works

  • maxProduct tracks the best positive chain
  • minProduct preserves large negatives for future flips
  • One pass, constant space

⏱ Complexity

  • Time: O(n)
  • Space: O(1)

🆚 Which approach should you use?

ApproachWhen to usePrefix–SuffixEasy to visualize, great for interviewsDP (Max–Min)More mathematical, very robust

Both are accepted, optimal, and interview-ready.

🎯 Interview Tip

If asked "Why track minimum product?":

Because a negative number can flip the smallest product into the largest one, so we must track both.

🧪 Test Runner

func maxProductMain() {
    let nums = [2, 3, -2, 4]
    print(maxProductII(nums)) // Output: 6
}

✅ Final Thoughts

  • This problem tests edge-case thinking
  • A great example where intuition beats brute force
  • Both solutions are O(n) and production-ready

If you're preparing for iOS interviews or DSA rounds, mastering this pattern is a big win 🚀