152. Maximum Product Subarray
On This Page
In this problem, we’re given an integer array
nums, and our task is to find the maximum product of a contiguous subarray. A subarray is a contiguous part of an array. The interesting part of this problem is that the array can contain both positive and negative numbers, so the maximum product can be obtained by a subarray ending at any index of the array.
A naive approach to this problem would be to calculate the product of all possible subarrays and return the maximum one. However, this would have a time complexity of O(n²), as there are n*(n+1)/2 subarrays of an array, where n is the length of the array.
This would be inefficient and time-consuming for large inputs.
We can solve this problem efficiently using Dynamic Programming.
The idea is to keep track of the maximum and minimum product ending at each position (as the array can contain negative numbers, and a negative number can become maximum when multiplied by another negative number).
We initialize two variables,
nums. Then for each number in the array (from the second number to the end), we calculate
min_prod using the formulas:
max_prod = max(nums[i], max_prod * nums[i], min_prod * nums[i]) min_prod = min(nums[i], max_prod * nums[i], min_prod * nums[i])
We also keep track of
res, which stores the maximum product of a subarray as a result.
max_prod is greater than
res, we update
res will hold the maximum product of a subarray.
- For each number in the array (from the second number to the end):
Here is a Python solution following the described approach:
def maxProduct(nums): if not nums: return 0 max_prod = min_prod = res = nums for num in nums[1:]: new_max = max(num, max_prod * num, min_prod * num) min_prod = min(num, max_prod * num, min_prod * num) max_prod = new_max res = max(res, max_prod) return res