Leetcode: Maximum Product Subarray

待我称王封你为后i 2022-08-07 09:59 46阅读 0赞

题目：  
Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array \[2,3,-2,4\],  
the contiguous subarray \[2,3\] has the largest product = 6.

这里的Product是乘积的意思。这道题的tag是Dynamic Programming，所以同样是动态规划的思想，找出局部和全局的递推关系。

思路：这道题和[上一道题：Maximum Subarray][Maximum Subarray]思路差不多。Maximum Subarray是求子数组和的最大值，这道题是求子数组乘积的最大值。计算最大的乘积同样要考虑负数的情况：一个很小的负数乘以一个负数，可能是一个很大的正数。所以这道题我们要设置两个局部最优变量，一个保存局部最大值，一个保存局部最小值（其实只有当这个局部最小值是负数的时候，才真正起作用）。  
它们有如下关系：  
copyMax = localMax  
localMax = max(max(localMax \* A\[i\], localMin \* A\[i\]), A\[i\])  
localMin = min(min(copyMax \* A\[i\], localMin \* A\[i\]), A\[i\])  
globalMax = max(localMax, globalMax)

C++代码：

class Solution
    {
    public:
        int maxProduct(int A[], int n)
        {
            if (n <= 0) return 0;
            int globalMax = A[0];
            int localMax = A[0];
            int localMin = A[0];
            int copyMax = localMax;
            for (int i = 1; i < n; i++)
            {
                copyMax = localMax;
                localMax = max(max(localMax * A[i], localMin * A[i]), A[i]);
                localMin = min(min(copyMax * A[i], localMin * A[i]), A[i]);
                globalMax = max(localMax, globalMax);
            }
            return globalMax;
        }
    };

C\#代码：

public class Solution
    {
        public int MaxProduct(int[] A) 
        {
            if (A.Length <= 0) return 0;
            int globalMax = A[0];
            int localMax = A[0];
            int localMin = A[0];
            int copyMax = localMax;
            for (int i = 1; i < A.Length; i++)
            {
                copyMax = localMax;
                localMax = Math.Max(Math.Max(localMax * A[i], localMin * A[i]), A[i]);
                localMin = Math.Min(Math.Min(copyMax * A[i], localMin * A[i]), A[i]);
                globalMax = Math.Max(globalMax, localMax);
            }
            return globalMax;
        }
    }

Python代码：

class Solution:
        # @param A, a list of integers
        # @return an integer
        def maxProduct(self, A):
            size = len(A)
            if size <= 0:
                return 0
            globalMax = A[0]
            localMax = A[0]
            localMin = A[0]
            copyMax = localMax
            for i in range(1, size):
                copyMax = localMax
                localMax = max(max(localMax * A[i], localMin * A[i]), A[i])
                localMin = min(min(copyMax * A[i], localMin * A[i]), A[i])
                globalMax = max(globalMax, localMax)
            return globalMax

[Maximum Subarray]: http://blog.csdn.net/theonegis/article/details/44758475