Posted on

Description

Submission

class Solution {
public:
int maxProduct(vector& nums) {
if(nums.empty()) return 0;
int localMin = nums[0], localMax = nums[0], globalMax = nums[0];

    for(int i = 1; i < nums.size(); ++i) {    
        int tmp = max(nums[i], max(localMax * nums[i], localMin * nums[i]));
        localMin = min(nums[i], min(localMin * nums[i], localMax * nums[i]));
        localMax = tmp;
        globalMax = max(localMax, globalMax);
    }
    return globalMax;

}

};

References

  1. https://medium.com/@aliasav/algorithms-maximum-product-subarray-b09e520b4baf
  2. https://www.wikiwand.com/en/Maximum_subarray_problem
  3. https://leetcode.com/problems/maximum-product-subarray/discuss/841167/C%2B%2B-Super-Simple-and-Clean-Solution-O(n)
  4. https://www.geeksforgeeks.org/maximum-product-subarray/

Leave a Reply

Your email address will not be published. Required fields are marked *