Find Maximum Product Subarray Dynamic Programming - Optimal Approach

Given an array of integers (which may contain positive numbers, negative numbers, and zeros), your task is to find the maximum product that can be obtained from a contiguous subarray.

• You can choose any contiguous part of the array (including a single element).
• The subarray must have at least one element.

If the array is empty, the answer should be 0.

Understanding the Problem

We are given an array of integers. Our goal is to find the maximum product subarray — that is, the contiguous subarray that gives the largest product when its elements are multiplied together.

Unlike sum problems, multiplication has unique challenges:

• Multiplying two negative numbers gives a positive number.
• Multiplying any number with zero resets the product to zero.
• Negative numbers can reduce the product or, if paired well, create the maximum one.

Step-by-Step Solution Using Example

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

We go through the array one element at a time. At each step, we keep track of:

• maxProductEndingHere: The maximum product that ends at the current index.
• minProductEndingHere: The minimum product that ends at the current index.

This is important because a negative number might make a small (even negative) product become a large positive one when multiplied.

Step-by-step execution:

• Start with max = min = result = 2 (first number)
• Next, 3:
  • tempMax = max(3, 2*3, 2*3) = 6
  • tempMin = min(3, 2*3, 2*3) = 3
  • Update result = max(6, 2) = 6
• Next, -2:
  • tempMax = max(-2, 6*(-2), 3*(-2)) = max(-2, -12, -6) = -2
  • tempMin = min(-2, 6*(-2), 3*(-2)) = min(-2, -12, -6) = -12
  • Swap min and max because of negative
  • Update result = max(6, -2) = 6
• Next, 4:
  • tempMax = max(4, -2*4, -12*4) = max(4, -8, -48) = 4
  • tempMin = min(4, -2*4, -12*4) = min(4, -8, -48) = -48
  • Update result = max(6, 4) = 6

Final Answer = 6

Edge Case Handling

What happens in special cases?

• Array contains 0: Restart max and min at 0; product splits.
• All positive: Product of full array is maximum.
• All negative (even count): Product of entire array is maximum (negatives cancel).
• All negative (odd count): Drop one negative (either from start or end) to get maximum product.
• Single element: That is the result.
• Empty array: No subarray exists. Return 0.

Key Intuition for Beginners

• We are not just tracking the max product — we also track the min because it can become max after a negative.
• Think of zero as a wall. You can’t continue the product across it.
• Swapping min and max when we see a negative is a key trick.

Finally

This is a classic dynamic programming problem. At each step, you use previous results to decide your current best. You only need one pass through the array, so the time complexity is O(n).

By managing both the maximum and minimum product ending at each position, we can smartly deal with negatives and zeros to find the optimal subarray product.

1. Given an array arr of integers.
2. Initialize three variables: max_product = arr[0], min_product = arr[0], and result = arr[0].
3. Traverse the array from index 1:
4. → If the current element is negative, swap max_product and min_product.
5. → Update max_product as the maximum of current element and current element * max_product.
6. → Update min_product as the minimum of current element and current element * min_product.
7. → Update result as the maximum of result and max_product.
8. Return result as the final maximum product subarray.

O(1)

Explanation: The solution uses only a constant number of variables (max_product, min_product, result), so the space used does not grow with input size.