DATA STRUCTURES • ALGORITHMS

Maximum Product Subarray

Finding the contiguous subarray within a one-dimensional array of numbers which has the largest product. This requires tracking both min and max products due to negative numbers.

Time

O(N)

Space

O(1)

Key Principle 1

Tracks current min and max

Key Principle 2

Handles negative multipliers

Key Principle 3

Zeroes reset the product

Key Principle 4

Optimal O(N) single pass

MAX_PRODUCT_LAB
ARRAY:
Current Step
Initialize curMax, curMin at 1. Store overall maximum.
Playback
DP Variables ⠿
CUR MAX1
CUR MIN1
GLOBAL MAX4
Max Product Logic ⠿
1int curMax = 1, curMin = 1, res = arr[0];
2for (int x : arr) {
3    if (x == 0) { curMax = 1; curMin = 1; continue; }
4    int tmp = curMax * x;
5    curMax = max({x * curMax, x * curMin, x});
6    curMin = min({tmp, x * curMin, x});
7    res = max(res, curMax);
8}
2
[0]
3
[1]
-2
[2]
4
[3]

Loading Lab...