题目描述：

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.

题目大意：

从数组（至少包含一个数字）中找出一个连续的子数组，该子数组的乘积最大。

解题思路：

    简单动态规划：

• 用数组positive_max[i]维护原始数组前i个数的子数组乘积中正数的最大值
• 用数组negative_min[i]维护原始数组前i个数的子数组乘积中负数的最小值

状态转移方程为：

if A[x] > 0:
	positive_max[x] = max(positive_max[x - 1] * A[x], A[x])
	negative_min[x] = negative_min[x - 1] * A[x]
elif A[x] < 0:
	positive_max[x] = negative_min[x - 1] * A[x]
	negative_min[x] = min(positive_max[x - 1] * A[x], A[x])

Python代码如下：

maximum-product-subarray.py

class Solution:
	# @param A, a list of integers
	# @return an integer
	def maxProduct(self, A):
		ans = max(A)
		size = len(A)
		positive_max = [0 for x in range(size)]
		negative_min = [0 for x in range(size)]
		if A[0] > 0:
			positive_max[0] = A[0]
		elif A[0] < 0:
			negative_min[0] = A[0]
		for x in range(1, size):
			if A[x] > 0:
				positive_max[x] = max(positive_max[x - 1] * A[x], A[x])
				negative_min[x] = negative_min[x - 1] * A[x]
			elif A[x] < 0:
				positive_max[x] = negative_min[x - 1] * A[x]
				negative_min[x] = min(positive_max[x - 1] * A[x], A[x])
			if positive_max[x] and positive_max[x] > ans:
				ans = positive_max[x]
		return ans

Judge评测结果：Accepted 212ms

本文链接：http://bookshadow.com/weblog/2014/10/15/leetcode-maximum-product-subarray/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码