Maximum Product Subarray

Given an integer array, find the contiguous subarray with the largest product. A naive O(n^2) scan is too slow.

Function signature

func MaxProduct(nums []int) int

Inputs / outputs

• nums: non-empty array of integers.
• Return: maximum product of any contiguous subarray.

Example

nums = [2,3,-2,4]
Best subarray: [2,3] -> 6
Output: 6

Constraints

• 1 <= len(nums) <= 100_000

Core idea (near-solution)

Track both maximum and minimum products ending at each position because a negative number flips signs.

Invariant: maxProd and minProd are the best/worst products ending at i.

Algorithm (step-by-step)

1. Initialize maxProd = minProd = res = nums[0].
2. For each x in nums[1:]:
   • If x < 0, swap maxProd and minProd.
   • Update maxProd = max(x, maxProd*x).
   • Update minProd = min(x, minProd*x).
   • Update res with maxProd.
3. Return res.

Correctness sketch

• Invariant: maxProd and minProd are the best/worst products ending at i.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

Trace (hand walkthrough)

Example input:
nums = [2,3,-2,4]
Best subarray: [2,3] -> 6
Output: 6

Walk:
- start max=min=2, best=2
- val=3 -> max=6 min=3 best=6
- val=-2 -> max=-2 min=-12 best=6
- val=4 -> max=4 min=-48 best=6

Pitfalls to avoid

• Tracking only the max (fails with negative numbers).
• Resetting to 0 incorrectly.

Complexity

• Time: O(n).
• Extra space: O(1).

Implementation notes (Go)

• Swapping max/min on negative is the key correctness step.