Blind 75Medium

Maximum Product Subarray — Track Hi/Lo Products

Maintain both the highest and lowest running product because negative numbers can flip the sign of the result.

Dynamic ProgrammingArray

View problem on LeetCode

Problem Statement

Find the contiguous subarray within an array that has the largest product.

Why This Problem Matters

Extends Kadane’s algorithm ideas to multiplication where negatives invert ordering.
Trains you to track multiple states (max and min) simultaneously.
Highlights tricky edge cases involving zeros and negative numbers.

Thought Process

Recognise the Kadane analogy

Products behave like sums but require tracking both extremes because multiplying by a negative swaps them.

Swap on negatives

When encountering a negative number, exchanging hi and lo keeps the invariants correct.

Update running answers

At each index choose between starting fresh or extending the previous product.

Step-by-Step Reasoning

Initialise hi = lo = max = nums[0].
Iterate from index 1 onward.
If nums[i] is negative, swap hi and lo.
Update hi = max(nums[i], hi * nums[i]) and lo = min(nums[i], lo * nums[i]); refresh max.

Dry Run

nums = [2,3,-2,4]

hi progresses to 6, swap on -2, max ends at 6.

nums = [-2,0,-1]

Max stays at 0 because products involving negatives reset around zero.

Complexity Analysis

Time

O(n)

Space

O(1)

Why

Single pass with constant extra tracking variables.

Annotated Solution

JAVA

public class MaximumProductSubarray {
  public int maxProduct(int[] nums) {
    int hi = nums[0];
    int lo = nums[0];
    int max = nums[0];

    for (int i = 1; i < nums.length; i += 1) {
      int num = nums[i];
      if (num < 0) {
        int tmp = hi;
        hi = lo;
        lo = tmp;
      }

      hi = Math.max(num, hi * num);
      lo = Math.min(num, lo * num);
      max = Math.max(max, hi);
    }

    return max;
  }
}

Tracking both the best and worst running products accounts for the fact that multiplying by a negative flips signs.

Common Pitfalls

Forgetting to swap hi/lo on negatives yields incorrect products.
Not handling arrays of length one can cause index errors.
Ignoring zeros fails to reset the running product correctly.

Follow-Up Questions

How would you return the actual subarray boundaries?
Can you adapt this to maximum product of length k exactly?

Key Takeaways

When signs matter, keep both extremes in your state.

Swapping state variables is an elegant way to handle negative flips.

Zeros reset the search, just like negatives reset Kadane’s sum.