最大乘积，最大和连续子数组

最大连续乘积子数组

遍历数组时计算当前最大值&＃xff0c;不断更新
令imax为当前最大值&＃xff0c;则当前最大值为 imax &＃61; max(imax * nums[i], nums[i])
由于存在负数&＃xff0c;那么会导致最大的变最小的&＃xff0c;最小的变最大的。因此还需要维护当前最小值imin&＃xff0c;imin &＃61; min(imin * nums[i], nums[i])
当负数出现时则imax与imin进行交换再进行下一步计算
时间复杂度&＃xff1a;O(n)

class Solution {
public:int maxProduct(vector<int>& nums) {int ans &＃61; -999999999; //这个是用来保存最大值int Max&＃61;1,Min&＃61;1; //这里都设置为1 &＃xff0c;原因在下面两行max,min函数中for(int i&＃61;0;i<nums.size();&＃43;&＃43;i){if(nums[i]<0){Max^&＃61;Min^&＃61;Max^&＃61;Min;}Max &＃61; max(Max*nums[i],nums[i]);Min &＃61; min(Min*nums[i],nums[i]);ans &＃61; max(ans,Max);}return ans;}
};


最大连续子数组和

思路&＃xff1a;

这里只要一个循环就搞定&＃xff0c;从头到尾遍历&＃xff0c;用一个变量记录num当前所到的值是正数还是负数&＃xff0c;如果是负数&＃xff0c;就直接把之前的值去掉&＃xff0c;把当前的值赋值给num变量即可&＃xff0c;然后用一个全局变量保存最大值。

class Solution {
public:int maxSubArray(vector<int>& nums) {if(nums.size()&＃61;&＃61;0) return 0;int ans&＃61;-99999999;int num&＃61;0;for(int i&＃61;0;i<nums.size();&＃43;&＃43;i){if(num < 0){num &＃61; nums[i];}else{num &＃43;&＃61; nums[i];}if(ans<num){ans &＃61; num;}}return ans;}
};


力扣上还有一种复杂的解法&＃xff0c;可以学习了解&＃xff0c;就是线段树的原理。