Leetcode 152. Maximum Product Subarray

Maximum Product Subarray :

給定一個數組 nums，找到一個子數組相乘可以得到最大乘積

Python

array可能有負數，所以如果nums[i]值小於0，乘了以後就會變負數，要把local_max跟local_min交換，之後迴圈找出最大值。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:

        global_max,local_max,local_min=nums[0],nums[0],nums[0]

        for i in range(1,len(nums)):
        #nums[i]值小於0，乘了以後就會變負數，要把local_max跟local_min交換
            if nums[i]<0:
                local_max,local_min=local_min,local_max
            local_max=max(nums[i],nums[i]*local_max)
            local_min=min(nums[i],nums[i]*local_min)
            global_max=max(local_max,global_max)
        return global_max

C++

class Solution {
public:
	int maxProduct(vector<int>& nums) {
		if(nums.size() == 0) return 0;
		int res = nums[0];
		int maxv = nums[0], minv = nums[0];
		for(int i = 1; i < nums.size(); i++){
			if(nums[i] < 0){
			swap(maxv, minv);
			}
		maxv = max(nums[i], maxv * nums[i]);
		minv = min(nums[i], minv * nums[i]);
		res = max(res, maxv);
	}
	return res;
	}
};