Solution For Maximum Product Subarray
The Maximum Product Subarray problem is a classic problem in computer science. It can be solved using dynamic programming.
The problem statement is as follows:
Given an array of integers, find the contiguous subarray within it that has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product 6.
Solution:
We can solve this problem using dynamic programming. The key to solving this problem is recognizing that the maximum product subarray can be computed from the maximum product of the subarray ending at each position.
We will maintain two arrays:
max_product[i]
stores the maximum product of the subarray ending at position i.min_product[i]
stores the minimum product of the subarray ending at position i.
We will then update these arrays at each position using the following equations:
max_product[i] = max(nums[i], max_product[i-1] * nums[i], min_product[i-1] * nums[i])
min_product[i] = min(nums[i], max_product[i-1] * nums[i], min_product[i-1] * nums[i])
The max_product[i]
and min_product[i]
represent the maximum and minimum product of subarrays ending at position i
, respectively. If the current number nums[i]
is positive, then the maximum and minimum product of subarrays ending at position i
is either nums[i]
itself or the maximum and minimum product of subarrays ending at position i-1
times nums[i]
. If nums[i]
is negative, then the maximum and minimum product of subarrays ending at position i
is either nums[i]
itself or the minimum and maximum product of subarrays ending at position i-1
times nums[i]
.
Finally, we return the maximum value in max_product
.
Here is the implementation of the solution in Python:
“`
def maxProduct(nums: List[int]) -> int:
max_product = [0] * len(nums)
min_product = [0] * len(nums)
max_product[0] = nums[0]
min_product[0] = nums[0]
for i in range(1, len(nums)):
if nums[i] >= 0:
max_product[i] = max(nums[i], max_product[i-1] * nums[i])
min_product[i] = min(nums[i], min_product[i-1] * nums[i])
else:
max_product[i] = max(nums[i], min_product[i-1] * nums[i])
min_product[i] = min(nums[i], max_product[i-1] * nums[i])
return max(max_product)
“`
The time complexity of this solution is O(N), where N is the length of the input array. The space complexity is O(N), since we use two arrays to store the maximum and minimum product of subarrays ending at each position.
Step by Step Implementation For Maximum Product Subarray
class Solution { public int maxProduct(int[] nums) { // keep track of the maximum positive product seen so far // and the minimum negative product seen so far int maxPos = nums[0]; int minNeg = nums[0]; int maxSoFar = nums[0]; for (int i = 1; i < nums.length; i++) { // update maximum positive product seen so far (if current num is positive) if (nums[i] > 0) { maxPos = Math.max(maxPos * nums[i], nums[i]); // update minimum negative product seen so far (if current num is positive) minNeg = Math.min(minNeg * nums[i], nums[i]); } // update maximum positive product seen so far (if current num is negative) else if (nums[i] < 0) { int temp = maxPos; maxPos = Math.max(minNeg * nums[i], nums[i]); // update minimum negative product seen so far (if current num is negative) minNeg = Math.min(temp * nums[i], nums[i]); } // update result if necessary maxSoFar = Math.max(maxPos, maxSoFar); } return maxSoFar; } }
class Solution: def maxProduct(self, nums: List[int]) -> int: # keep track of the maximum and minimum product so far max_product = nums[0] min_product = nums[0] # also keep track of the overall maximum product overall_max = nums[0] for i in range(1, len(nums)): # update maximum and minimum product so far, given the current number curr_max = max(max_product * nums[i], min_product * nums[i], nums[i]) curr_min = min(max_product * nums[i], min_product * nums[i], nums[i]) # update overall maximum overall_max = max(overall_max, curr_max) # update maximum and minimum product so far for next iteration max_product = curr_max min_product = curr_min return overall_max
/** * @param {number[]} nums * @return {number} */ // Kadane's Algorithm var maxProduct = function(nums) { let maxSoFar = nums[0]; let minSoFar = nums[0]; let max = nums[0]; for(let i=1; i class Solution { public: int maxProduct(vector& nums) { int n = nums.size(); int max_so_far = nums[0]; int min_so_far = nums[0]; int res = nums[0]; for (int i = 1; i < n; i++) { if (nums[i] == 0) { max_so_far = 1; min_so_far = 1; continue; } int curr_max = max(max_so_far*nums[i], min_so_far*nums[i]); int curr_min = min(max_so_far*nums[i], min_so_far*nums[i]); max_so_far = curr_max; min_so_far = curr_min; res = max(res, max_so_far); } return res; } }; public int MaxProduct(int[] nums) { // keep track of the maximum product seen so far // and the minimum product seen so far int maxSoFar = nums[0]; int minSoFar = nums[0]; // overall maximum product int maxProduct = nums[0]; for (int i = 1; i < nums.Length; i++) { // update maximum and minimum products seen so far int currMax = Math.Max(nums[i], Math.Max(maxSoFar * nums[i], minSoFar * nums[i])); int currMin = Math.Min(nums[i], Math.Min(maxSoFar * nums[i], minSoFar * nums[i])); // update overall maximum product maxProduct = Math.Max(maxProduct, currMax); // update maximum and minimum products seen so far for next iteration maxSoFar = currMax; minSoFar = currMin; } return maxProduct; }