Maximum Product Subarray

Explanation

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

For example:

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

Output:
6

The subarray [2, 3] gives the maximum product.

2 × 3 = 6

Problem Statement

Given an integer array nums, find a contiguous non-empty subarray that has the largest product and return the product.

Features

• Finds the maximum product
• Handles positive and negative numbers
• Handles zero values
• Uses a single traversal
• Efficient solution

How It Works

The program keeps track of two values:

• currentMax stores the largest product ending at the current position.
• currentMin stores the smallest product ending at the current position.

The minimum value is important because multiplying a negative number by a negative value can produce a large positive value.

When the current number is negative, currentMax and currentMin are swapped before updating them.

The maximum product found during the traversal is stored in maxProduct.

Technologies Used

• Arrays
• Loops
• Conditional statements
• Methods
• Mathematical operations

Data Structure Used

The program uses an integer array to store the input values.

Methods Used

maxProduct()

Finds and returns the maximum product of a contiguous subarray.

main()

Creates the sample input, calls maxProduct(), and displays the result.

Program Flow

Start
↓
Read array
↓
Initialize current maximum
↓
Initialize current minimum
↓
Traverse array
↓
Check for negative value
↓
Swap maximum and minimum if needed
↓
Update current maximum
↓
Update current minimum
↓
Update maximum product
↓
Return result
↓
End

Sample Input

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

Sample Output

Maximum Product: 6

Time Complexity

O(n)

The array is traversed once.

Space Complexity

O(1)

Only a few variables are used.

Key Learning

This problem teaches how to handle negative numbers by tracking both the maximum and minimum products during array traversal.

File Location

Arrays/MaximumProductSubarray.java

Repository Structure

Maximum-Product-Subarray/
├── README.md
└── Arrays/
    └── MaximumProductSubarray.java

Author

V.Harini