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.