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