152. Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

• new solution update 2022.02.06

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

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.empty())
            return 0;
        
        int maxVal = nums[0], minVal = nums[0];
        int res = nums[0];
        
        for(int i = 1; i < nums.size(); ++i) {
            int cur = nums[i];
            int tempMaxVal = max(cur, max(maxVal * cur, minVal * cur));
            minVal = min(cur, min(maxVal * cur, minVal * cur));
            
            maxVal = tempMaxVal;
            
            res = max(res, maxVal);
        }

        return res;
    }
};