Maximum Product Subarray

Find the contiguous subarray with the largest product and return that product.

A way to picture it

Negative numbers are mirror portals: step through one and the biggest product becomes the smallest, and the smallest becomes the biggest. So you carry both, because one portal later the tiny one might be the giant.

How to approach it

Track the maximum AND the minimum product ending at each position. For each number, the new max is the largest of x, max × x and min × x.

Example

Input: {"nums":[2,3,null,4]}. Output: 6.

Complexity: O(n) time and O(1) space. One pass with three running values.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.