152. 乘积最大子数组

152. 乘积最大子数组 - 力扣（LeetCode）

class Solution {
public:
  int maxProduct(vector<int>& nums) {
    // We consider both Max and Min. Keep in mind that Min can be negative.
    int Max = nums.front();
    int Min = nums.front();
    int Product = nums.front();
    for (int i = 1; i < nums.size(); ++i) {
      // We need to store the temporary Max and Min values, since the following
      // computations must be done NONsequential.
      int Max_ = Max, Min_ = Min;
      // While we traverse the vector, we do a three-way max/min to implicitly
      // check if current value is negative. If so, then we'll update the value
      // by using Min * nums[i], which is positive; otherwise by using Max.
      Max = max(nums[i], max(Max_ * nums[i], Min_ * nums[i]));
      Min = min(nums[i], min(Max_ * nums[i], Min_ * nums[i]));
      Product = max(Product, Max);
    }
    return Product;
  }
};

这题确实基本上是 53. 最大子数组和的延续。不同之处在于为了解决「负负得正」的问题，我们需要在遍历的过程中维护两个序列，分别是最大正数、最小负数，并利用 max() 来隐式地考虑对于有当前的 nums[i]，是它自己比较大、它乘上正数比较大（此时 nums[i] 必然是正数）、还是乘上负数比较大（此时 nums[i] 必然是负数）。

这题在编写的时候要注意的一点在于计算 Max 和 Min 时，两个操作是需要同时完成的，也就是说我们不能在计算完 Max 之后就直接把 Max 修改掉了，因为后面 Min 算的时候还是得用原数的，所以得创建两个临时变量来做这件事情。

二刷

class Solution {
public:
  int maxProduct(vector<int>& nums) {
    int Max = nums.front(), Min = nums.front();
    int Product = nums.front();
    for (int i = 1; i < nums.size(); ++i) {
      int MaxTemp = Max, MinTemp = Min;
      // Three-way comparison: Self, Self * Max, and Self * Min.
      Max = max(nums[i], max(nums[i] * MaxTemp, nums[i] * MinTemp));
      Min = min(nums[i], min(nums[i] * MaxTemp, nums[i] * MinTemp));
      // In fact we can get maximum and minimum subarray simultaneously, but we
      // only need the maximum value in this question.
      Product = max(Product, Max);
    }
    return Product;
  }
};