[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.

题目大意:

从数组(至少包含一个数字)中找出一个连续的子数组,该子数组的乘积最大。

解题思路:

    简单动态规划:

  • 用数组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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

暂无评论

张贴您的评论