Maximum Product Subarray

Difficulty: Hard · Topic: Greedy algorithms

Given an integer array nums, return the largest product of any contiguous subarray. The Kadane twist: a negative number flips big↔small, so carry both the running max and running min; multiplying the min by a negative can become the new max.

Examples

max_product_subarray([2,3,-2,4])
→ 6

[2,3] → 6.

max_product_subarray([-2,0,-1])
→ 0

Target complexity: time O(n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.