遍历数组内的元素
求出以当前元素为结尾的所有子数组的最大乘积
再求全局最大值
以当前元素为结尾的最大乘积有两种可能
1,只有当前元素
2,包含前一个位置
由于元素存在负数,而负数*负数是正数,所以每一位记录最大乘积的同时还要记录最小乘积(如果元素是负数,可能乘以上一位的最小乘积得到的结果最大)
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = INT_MIN;
int last_max = 1, last_min = 1; // 初始的设置为1,和下一位相乘时不会影响
for(auto& num : nums){
int a = last_max * num, b = last_min * num;
last_max = max(num, max(a, b)); // 维护最大乘积
last_min = min(num, min(a, b)); // 维护最小乘积
res = max(last_max, res); // 取全局最大乘积
}
return res;
}
};