leetcode152-- Maximum Product Subarray

leetcode152-- Maximum Product Subarray

题目

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

这个的意思是求连续的最大子数组的积,不好弄的地方是,有可能出现0,也有可能出现负数,所以最大值和最小值都要维护,然后针对新遇到的数字是正数还是负数再进行更新,

解答如下


class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        res = nums[0]  # 注意这时候当res改变的时候maximum minimum并不会随之发生改变
        maximum = res
        minimum = res 
        
        
        # maximum代表以当前的位置为结尾的连续的子数组中的最大的积
        # minimum 代表的是最小的。

        for i in range(1,len(nums)):
            if nums[i]>0:
                # 如果当前的这个数字是正数,
                maximum = max(maximum*nums[i], nums[i])
                minimum = min(minimum*nums[i], nums[i])
            else:
                temp = maximum
                
                maximum = max(minimum*nums[i], nums[i])
                minimum = min(temp*nums[i], nums[i])
                
            res = max(res, maximum)
            
        return res
        
        

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦