152. Maximum Product Subarray

📝 Problem Details

• Title: 152. Maximum Product Subarray
• Link: https://leetcode.com/problems/maximum-product-subarray/
• Difficulty: Medium
• Tags/Categories: Dynamic-Programming

input array nums find a subarray that has the largest product return the product (result)

💭What Were My Initial Thoughts?

- similar to the problem maximum subarray
- kadanes algorithm could be beneficial to get something close to a linear solution

- the maximum product instead of maximum sum introduces the issue of negative numbers resulting in positive integers
- the presence of zeros in the array also break the subarray product (set it back to 0)

💡 Explanation of Solution

- track both maxProduct and minProduct at each step
- swap maxProduct and minProduct when encountering a negative number
- reset when encountering a zero

⌛ Complexity Analysis

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

💻 Implementation of Solution

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.empty()) return 0;
 
        int maxProduct = nums[0];
        int minProduct = nums[0];
        int result = nums[0];
 
        for(int i=1; i < nums.size(); i++) {
            if(nums[i] < 0) swap(maxProduct, minProduct);  // Swap when negative
 
            maxProduct = max(nums[i], maxProduct * nums[i]);  // Best product ending at i
            minProduct = min(nums[i], minProduct * nums[i]);  // Worst product ending at i
 
            result = max(result, maxProduct); // track global max product
        }
        return result;
    }
};