题目描述
给定一个double类型的数组arr,其中的元素可正可负可0,返回子数组累乘的最大乘积。例如arr=[-2.5,4,0,3,0.5,8,-1],子数组[3,0.5,8]累乘可以获得最大的乘积12,所以返回12。
class Solution:
def maxProduct(self , arr ):
# write code her
n=len(arr)
dp_min=[0 for _ in range(n)]
dp_max=[0 for _ in range(n)]
dp_min[0]=dp_max[0]=arr[0]
for i in range(1,n):
dp_max[i]=max(arr[i],arr[i]*dp_max[i-1],arr[i]*dp_min[i-1])
dp_min[i]=min(arr[i],arr[i]*dp_max[i-1],arr[i]*dp_min[i-1])
return max(dp_max)