Max Product Subarray [Kadanes similar]

152.Maximum Product Subarray

Array

Dynamic Programming

Math

Problem Statement:

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

Example:

Input:

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

→

Output:

6

Algorithm:

1. Track both max and min products
2. Handle positive and negative numbers
3. Swap max/min when negative number
4. Keep global maximum result

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public int maxProduct(int[] nums) {
    int res, max, min;
    res = max = min = nums[0];  // Initialize all with first element
    
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > 0) {
            max = Math.max(nums[i], nums[i] * max);  // Update max for positive numbers
            min = Math.min(nums[i], nums[i] * min);
        } else {
            int temp = max;  // Temp needed as max changes
            max = Math.max(nums[i], nums[i] * min);
            min = Math.min(nums[i], nums[i] * temp);
        }
        
        res = Math.max(max, res);  // Keep track of global maximum
    }
    
    return res;    
}

Python Solution:

def maxProduct(self, nums: List[int]) -> int:
    result = curr_max = curr_min = nums[0]
    
    for num in nums[1:]:
        if num > 0:
            curr_max, curr_min = max(num, curr_max * num), min(num, curr_min * num)
        else:
            temp = curr_max
            curr_max = max(num, curr_min * num)
            curr_min = min(num, temp * num)
            
        result = max(result, curr_max)
        
    return result

C++ Solution:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0], curr_max = nums[0], curr_min = nums[0];
        
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] > 0) {
                curr_max = max(nums[i], curr_max * nums[i]);
                curr_min = min(nums[i], curr_min * nums[i]);
            } else {
                int temp = curr_max;
                curr_max = max(nums[i], curr_min * nums[i]);
                curr_min = min(nums[i], temp * nums[i]);
            }
            
            res = max(res, curr_max);
        }
        
        return res;
    }
};