LeetCode 152. 乘积最大子数组

152. 乘积最大子数组 - 力扣（LeetCode） (leetcode-cn.com)

目录

运行结果 ​

分析

代码

---

运行结果

 ​​​​​​​ 分析

遍历整个数组，对于每个元素，我们希望得出以它为最后一个因数的最大乘积，在所有这些最大乘积中选出最大者。如果当前位置的元素为正数，我们希望它前面元素的乘积为正数，且越大越好；如果当前位置的元素为负数，我们希望它前面元素的乘积为负数，且越小越好。

因此，我们维护两个变量：maxPro记录以当前位置元素为最后一个因数的最大乘积，minPro记录以当前位置元素为最后一个因数的最小乘积。

代码

class Solution {
public:
    int maxProduct(vector& nums) {
        int maxPro = nums[0], minPro = nums[0];
        int max_product = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            int xP = maxPro * nums[i];
            int iP = minPro * nums[i];
            maxPro = max(max(xP, iP), nums[i]);        //当当前位置的元素为正数时，我们希望它乘以一个正的，尽可能大的数
            minPro = min(min(xP, iP), nums[i]);        //当当前位置的元素为负数时，我们希望它乘以一个负的，尽可能小的数
            max_product = max(max_product, maxPro);
        }
        return max_product;
    }
};