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

2021-06-22 08:04

阅读：625

标签：++ none NPU least ber lan title tput example

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.

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

解法：DP，用2个dp数组分别记录到i时的最大乘积和最小乘积，因为下一个数字如果为负数就可以把最小的乘积是负的变成正的最大值。

Java:

public int maxProduct(int[] A) {
   assert A.length > 0;
   int max = A[0], min = A[0], maxAns = A[0];
   for (int i = 1; i

Python:

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:

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: wo

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++:

class Solution {
public:
    int maxProduct(vector& nums) {
        if (nums.empty()) return 0;
        int res = nums[0], mn = nums[0], mx = nums[0];
        for (int i = 1; i

C++:

class Solution {
public:
    int maxProduct(vector& nums) {
        int res = nums[0], mx = res, mn = res;
        for (int i = 1; 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& nums) {
        int res = nums[0], mx = res, mn = res;
        for (int i = 1; i

C++:　　

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

类似题目：

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

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

标签：++ none NPU least ber lan title tput example

原文地址：https://www.cnblogs.com/lightwindy/p/9678602.html

上一篇：python3小实例

下一篇：06_zookeeper原生Java API使用

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[LeetCode] 152. Maximum Product Subarray 求最大子数组乘积
文章链接：http://soscw.com/essay/97285.html

亲，登录后才可以留言！

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

评论

热门文章

推荐文章

最新文章

置顶文章