题目描述
核心思想:记录当前的最大值和最小值。
因为,如果遇到负数,那么当前的最大值变成最小值,最小值会变成,最大值。
所以只需要记录当前最小值和最大值即可,不断的更新答案res。
C++ 代码
class Solution {
public:
int maxProduct(vector<int>& nums) {
if (nums.empty()) return 0;
int maxv = nums[0], minv = nums[0], res = nums[0];
for (int i = 1; i < nums.size(); i ++) {
int mx = maxv, mn = minv;
maxv = max(nums[i], max(nums[i] * mx, nums[i] * mn));// 如果mx和mn为0,那么此时最大值为nums[i];
minv = min(nums[i], min(nums[i] * mx, nums[i] * mn));
res = max(res, maxv);
}
return res;
}
};
为什么最大值和最小值都要存一个
nums[i]
?//乘积最大化:因此需要维护之前的最大值、最小值。因为会出现负负等正的情况
public int maxProduct(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int max = nums[0];
int min = nums[0];
int res = nums[0];
for(int i = 1;i < nums.length;i++){
//判断当前的数,如果是小于0的话,那么 max * nums[i] < min * nums[i]。所以交换max min
if(nums[i] < 0){
int temp = max;
max = min;
min = temp;
}
min = Math.min(nums[i], minnums[i]);
max = Math.max(nums[i], maxnums[i]);
res = Math.max(res, max);
}
return res;
}