Introduction

The Maximum Product Subarray problem involves finding the contiguous subarray that has the largest product.

Given an integer array arr[], the task is to find:

  • the contiguous subarray having maximum product
  • and return that product

Unlike Maximum Subarray Sum:

  • multiplication with negative numbers can completely change the result

This problem helps in understanding:

  • product-based traversal
  • handling negative numbers
  • dynamic tracking
  • optimization techniques

Example

Input: arr[] = [2,3,-2,4]Output: 6
Explanation:
Subarray:
[2,3]
Product = 6
This is the maximum product subarray.

Input: arr[] = [-2,0,-1]
Output: 0
Explanation:
Possible products:
[-2] = -2
[0] = 0
[-1] = -1
Maximum Product = 0

Constraints

 1 <= n <= 2 * 10^4 -10 <= arr[i] <= 10

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Generate all possible subarrays
  2. Calculate the product of every subarray
  3. Track maximum product

This approach is easy to understand but repeated product calculations increase time complexity.

Steps

  1. Traverse all starting indices.
  2. Generate subarrays from every index.
  3. Calculate current product.
  4. Update maximum product.
  5. Return final answer.

Dry Run

Input Array:[2,3,-2,4]

Start from 2:
Current Product = 2
Maximum Product = 2

Multiply by 3:
Current Product = 6
Maximum Product = 6

Multiply by -2:
Current Product = -12

Multiply by 4:
Current Product = -48

Continue traversal...

Final Result:
6

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)
Explanation:
All possible subarrays are generated and processed.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Approach 2 : Optimized Solution

Explanation

The optimized solution keeps track of:

  1. Maximum product till current index
  2. Minimum product till current index

Why minimum product?

Because:

  • multiplying two negative numbers can produce a large positive product

So:

  • minimum product can suddenly become maximum

Steps

  1. Initialize:
    • max_product
    • min_product
    • answer
  2. Traverse the array.
  3. If current number is negative:
    • swap max and min products
  4. Update:
    • current maximum product
    • current minimum product
  5. Update final answer.

Dry Run

Input Array:[2,3,-2,4]
Initially:
max_product = 2
min_product = 2
answer = 2

Traverse 3:
max_product = 6
min_product = 3
answer = 6

Traverse -2:
Negative number found
Swap max and min

max_product = -2
min_product = -12
answer = 6

Traverse 4:
max_product = 4
min_product = -48

Final Result:
6

Optimized Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Each element is processed once.

Space Complexity: O(1)
Explanation:
Only variables are used for tracking products.

Edge Cases

  1. Array contains zeros
  2. Array contains all negative numbers
  3. Array contains one element
  4. Product becomes very large
  5. Maximum product contains negative numbers

Why This Problem is Important

This problem helps in understanding:

  1. Product-based traversal
  2. Handling negative numbers
  3. Dynamic tracking
  4. Greedy optimization
  5. State maintenance

It is one of the most important advanced array interview problems.

Real-World Applications

Product optimization concepts are used in:

  1. Financial growth analysis
  2. Statistical modeling
  3. Signal processing
  4. Data trend analysis
  5. Performance analytics

Common Mistakes

  1. Forgetting minimum product tracking
  2. Incorrect swap logic
  3. Ignoring negative numbers
  4. Resetting products incorrectly

Interview Tips

Interviewers often expect:

  1. O(n) optimized solution
  2. Proper negative number handling
  3. Maximum and minimum tracking explanation

Always explain why minimum product is necessary.

Related Questions

  1. Maximum Subarray
  2. Circular Subarray Sum
  3. Product Except Self
  4. Kadane’s Algorithm
  5. Maximum Sum Rectangle

Final Takeaway

The Maximum Product Subarray problem is a fundamental optimization problem that teaches product-based traversal and handling negative number behavior efficiently. Understanding this problem builds a strong foundation for advanced dynamic programming and array optimization interview problems.