[LeetCode] 152. Maximum Product Subarray 求最大子数组乘积

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 152. 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.html

Example 1:java

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

Example 2:python

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

53. Maximum Subarray 的变形,求和的时候,遇到0不会改变最大值,遇到负数也只是会减少最大值。而在求最大子数组乘积,遇到0会使整个乘积为0,遇到负数会使最大乘积变成最小乘积。数组

解法:DP,用2个dp数组分别记录到i时的最大乘积和最小乘积,由于下一个数字若是为负数就能够把最小的乘积是负的变成正的最大值。post

Java:url

public int maxProduct(int[] A) {
   assert A.length > 0;
   int max = A[0], min = A[0], maxAns = A[0];
   for (int i = 1; i < A.length; i++) {
      int mx = max, mn = min;
      max = Math.max(Math.max(A[i], mx * A[i]), mn * A[i]);
      min = Math.min(Math.min(A[i], mx * A[i]), mn * A[i]);
      maxAns = Math.max(max, maxAns);
   }
   return maxAns;
}

Python:code

class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxProduct(self, A):
        global_max, local_max, local_min = float("-inf"), 1, 1
        for x in A:
            local_max, local_min = max(x, local_max * x, local_min * x), min(x, local_max * x, local_min * x)
            global_max = max(global_max, local_max)
        return global_max

Python:htm

class Solution2:
    # @param A, a list of integers
    # @return an integer
    def maxProduct(self, A):
        global_max, local_max, local_min = float("-inf"), 1, 1
        for x in A:
            local_max = max(1, local_max)
            if x > 0:
                local_max, local_min = local_max * x, local_min * x
            else:
                local_max, local_min = local_min * x, local_max * x
            global_max = max(global_max, local_max)
        return global_max  

Python: woblog

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp1 = [0] * len(nums)
        dp1[0] = nums[0]
        dp2 = [0] * len(nums)
        dp2[0] = nums[0]
        res = dp1[0]
        for i in xrange(1, len(nums)):
            dp1[i] = max(dp1[i-1] * nums[i], dp2[i-1] * nums[i], nums[i])
            dp2[i] = min(dp1[i-1] * nums[i], dp2[i-1] * nums[i], nums[i])
            res = max(res, dp1[i])
            
        return res    

C++:get

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

C++:

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

C++:

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

C++:  

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

    

 

相似题目:

[LeetCode] 53. Maximum Subarray 最大子数组

 

All LeetCode Questions List 题目汇总