LeetCode 152 · Medium · 1-D Dynamic Programming

Maximum Product Subarray

Find the non-empty run of neighbouring numbers in nums whose product is largest, and return that product.

O(n)time
O(1)space
max and minending here, swap on negatives

comma-separated integers · 1–10 values · −9 to 9 each

curMax / curMin column j = largest and smallest product of a run ending at nums[j] · arrows: where each came from

n < 0: max and min trade places
public int maxProduct(int[] nums) { int res = Arrays.stream(nums).max().getAsInt(); int curMin = 1, curMax = 1; for (int n : nums) { int tmp = curMax * n; curMax = Math.max(Math.max(n * curMax, n * curMin), n); curMin = Math.min(Math.min(tmp, n * curMin), n); res = Math.max(res, curMax); } return res;}
n
—
curMax
1
curMin
1
res
—

Why it works

  1. Brute force multiplies every run: O(n²) start and end pairs, keeping a running product per start: O(n²) time.
  2. Keep the extremes, not just the best: a negative number flips the order, so the most negative product so far can become the largest one step later. Track both curMax and curMin of runs ending at the current number; the new extremes come from n · curMax, n · curMin or n alone.
  3. One pass, three numbers: each step reads only the previous column, so O(n) time and O(1) space. The arrows show the swap: on a negative n, the max arrow comes from the min row and the min arrow from the max row, unless n alone wins.
  4. Pitfall: overwrite curMax and then use it for curMin, and the min reads the new value. Save the old product in tmp first. A zero resets both extremes to 0, and the n candidate restarts the run after it.
  5. Start res at the largest single number, not 0 or 1: for [-3] the answer is −3.
  6. Related: Maximum Subarray (Kadane) is the same idea with sums, where only the max is needed because adding never flips order.