本文共 2346 字，大约阅读时间需要 7 分钟。

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.

一开始的思路是直接用二维数组，递推关系式为：dp[i][j] =  dp[i][j - 1] * nums[j];代码如下：

public class Solution {    public int maxProduct(int[] nums) {		int len = nums.length;		int[][] dp = new int[len][len];		int tempMax = Integer.MIN_VALUE;				for(int i = 0; i < len; i++){			dp[i][i] = nums[i];			if(tempMax < dp[i][i])				tempMax = dp[i][i];		}				for(int i = 0; i < len; i++)			for(int j = i + 1; j < len; j++){				dp[i][j] = dp[i][j - 1] * nums[j];				if(dp[i][j] > tempMax)					tempMax = dp[i][j];			}		return tempMax;    }}

都跑到最后一个了，有点不甘心，看看测试数据，发现没有0啊之类的，就想了个有点投机取巧的办法，就是看nums有多少个负数，若是偶数个且没有0就好办了，代码如下：

public class Solution {   public int maxProduct(int[] nums) {		int len = nums.length;		int flag = 0;		boolean hasZero = false;				for(int i = 0; i < len; i++){			if(nums[i] < 0)				flag++;			if(!hasZero && nums[i] == 0)				hasZero = true;		}				if(!hasZero && flag % 2 == 0){			int result = 1;			for(int i = 0; i < len; i++)				result = result * nums[i];			return result;		}						int[][] dp = new int[len][len];		int tempMax = Integer.MIN_VALUE;				for(int i = 0; i < len; i++)			for(int j = i; j < len; j++){				if(i == j)					dp[i][j] = nums[j];				else					dp[i][j] = dp[i][j - 1] * nums[j];				if(dp[i][j] > tempMax)					tempMax = dp[i][j];			}		return tempMax;    }}

上网搜别人的代码，好像有好几种解法，比较钟情的下面这种：计算乘积的过程中记录最大值和最小值（负数），若当前值乘以之前的最大（最小）值比当前值更小（更大），则将当前值设为起点，代码如下：

public class Solution {    public int maxProduct(int A[]) {        if(A==null||A.length==0) {	      return 0;	    }	    int maxProduct = A[0];	    int max_temp   = A[0];	    int min_temp   = A[0];	    	    for(int i=1;i

最近在学学python，就用python写了一遍这个算法，附上代码：

class Solution(object):    def maxProduct(self, nums):        """        :type nums: List[int]        :rtype: int        """        maxProduct = max_temp = min_temp = nums[0]        for i in range(1, len(nums)):            temp = [nums[i], nums[i] * min_temp, nums[i] * max_temp]            min_temp, max_temp = min(temp), max(temp)            maxProduct = max(max_temp, maxProduct)        return maxProduct

转载地址：http://klbvb.baihongyu.com/