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:

1. max_product[i] stores the maximum product of the subarray ending at position i.
2. 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:

1. max_product[i] = max(nums[i], max_product[i-1] * nums[i], min_product[i-1] * nums[i])
2. 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;
}