Leetcode: Maximum Product Subarray

题目： 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是求子数组和的最大值，这道题是求子数组乘积的最大值。计算最大的乘积同样要考虑负数的情况：一个很小的负数乘以一个负数，可能是一个很大的正数。所以这道题我们要设置两个局部最优变量，，一个保存局部最大值，一个保存局部最小值（其实只有当这个局部最小值是负数的时候，才真正起作用）。 它们有如下关系： 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{(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代码：

:size = len(A)if size <= 0:return 0globalMax = A[0]localMax = A[0]localMin = A[0]copyMax = localMaxfor i in range(1, size):copyMax = localMaxlocalMax = 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

真正的强者，不是流泪的人，而是含泪奔跑的人。