'''
152. Maximum Product Subarray
给定数组 nums，求出最大子数组的积
仍然使用动态规划的思想
维护2个数组，分别存储遍历到当前元素时的最大值和最小值
maxToCurr 从第0个元素一直到第i个元素(包含第i个元素)，子数组乘积的最大值
minToCurr 从第0个元素一直到第i个元素(包含第i个元素)，子数组乘积的最小值
product 输出的乘积最大值
状态转移方程：
在每次循环过程中：
maxToCurr[i+1]=max(maxToCurr[i]*nums[i],minToCurr*nums[i],nums[i])
minToCurr[i+1]=min(maxToCurr[i]*nums[i],minToCurr*nums[i],nums[i])
product=max(product,maxToCurr[i+1],minToCurr[i+1])
'''
class Solution:
def maxProduct(self, nums) -> int:
if len(nums)==0:
return 0
if len(nums)==1:
return nums[0]
maxToCurr=[nums[0] for _ in range(len(nums))]
minToCurr=[nums[0] for _ in range(len(nums))]
product=nums[0]
for i in range(1,len(nums)):
maxToCurr[i]=max(maxToCurr[i-1]*nums[i],minToCurr[i-1]*nums[i],nums[i])
minToCurr[i] = min(maxToCurr[i - 1] * nums[i], minToCurr[i - 1] * nums[i], nums[i])
product = max(product, maxToCurr[i], minToCurr[i])
return product
if __name__=="__main__":
# print(max(5,0,9))
print(Solution().maxProduct([2,-5,-2,-4,3]))
