Maximum Product Subarray — Solution & Editorial

Back to the Problem

Track BOTH the maximum and minimum product ending at each position (a negative factor swaps them); the running maximum is the answer.

Complexity: O(N)

Watch out: A negative number turns the smallest product into the largest — you must carry the min alongside the max.