152. Maximum Product Subarray

Leetcode link

解题思路

题目要求我们求乘积最大的连续子数组。

我们需要三个变量：

• max：保留相乘之后的最大值
• min：保留相乘之后的最小值（因为只要之后有负数，这一项可能会变成最大值）
• res：保留每次循环结束的最大值

算法步骤如下：

1. 循环数组，将数组的元素分别与 max，min 相乘
2. 比较 max，min，数组元素本身，将其中最大值赋值给 max（记得把原来的 max 保存成 temp）
3. 比较 temp，min，数组元素本身，将其中最小值赋值给 min
4. 比较 max 与 res ，将其中最大值赋值给 res
5. 继续步骤 1 直到循环结束

C++

class Solution {
 public:
  int maxProduct(vector<int>& nums) {
    int maximum = 1, minmum = 1, res = nums[0];
    for (int num : nums) {
      maximum *= num;
      minmum *= num;
      int temp = maximum;
      maximum = max({maximum, minmum, num});
      minmum = min({temp, minmum, num});
      res = res > maximum ? res : maximum;
    }
    return res;
  }
};

Javascript

var maxProduct = function(nums) {
    let max = 1, min = 1, res = nums[0];
    for(const num of nums) {
        max *= num;
        min *= num;
            // 保存起来，不然有可能本来 max 是最小值最后呗下一行更改了
        let temp = max;
        max = Math.max(max, min, num);
        min = Math.min(temp, min, num);
        res = max > res ? max : res;

    }
    return res;
};