⬅ Previous Topic
Find Length of Largest Subarray with 0 SumNext Topic ⮕
Binary Search in Array using Iteration⬅ Previous Topic
Find Length of Largest Subarray with 0 SumNext Topic ⮕
Binary Search in Array using IterationTopic Contents
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.
If the array is empty, the answer should be 0
.
arr
of integers.max_product = arr[0]
, min_product = arr[0]
, and result = arr[0]
.max_product
and min_product
.max_product
as the maximum of current element
and current element * max_product
.min_product
as the minimum of current element
and current element * min_product
.result
as the maximum of result
and max_product
.result
as the final maximum product subarray.def max_product_subarray(arr):
max_product = min_product = result = arr[0]
for num in arr[1:]:
if num < 0:
max_product, min_product = min_product, max_product
max_product = max(num, num * max_product)
min_product = min(num, num * min_product)
result = max(result, max_product)
return result
# Sample Input
arr = [2, 3, -2, 4]
print("Maximum Product Subarray:", max_product_subarray(arr))
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n) | In the best case, the array contains only positive numbers, and a single pass through the array is sufficient to compute the result. |
Average Case | O(n) | The algorithm always traverses the entire array once to keep track of current maximum and minimum products due to possible negative values. |
Worst Case | O(n) | Even if the array has many sign changes and zeros, the algorithm must still iterate over every element to track product variations. |
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.
⬅ Previous Topic
Find Length of Largest Subarray with 0 SumNext Topic ⮕
Binary Search in Array using IterationYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.