【中等】152. 乘积最大子数组
每日一道力扣，一起刷起来！
题目描述
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
题目来源：力扣（LeetCode），著作权归领扣网络所有。
解题思路
这道题采用暴力法时间会超时，应该考虑采用动态规划来做。
设dp表示前i个数中的最大乘积，maxn表示以第i-1个字符结尾的最大乘积。
由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值，设minn表示以第i-1个字符结尾的最小乘积。
则状态转移方程：
dp = max(dp,maxn*nums[i],minn*nums[i],nums[i])
class Solution(object):def maxProduct(self, nums):""":type nums: List[int]:rtype: int"""dp,maxn,minn = nums[0],nums[0],nums[0]# dp表示前i个数中的最大乘积，maxn表示以第i-1个字符结尾的最大乘积,minn表示以第i-1个字符结尾的最小乘积for i in range(1,len(nums)):dp = max(dp,maxn*nums[i],minn*nums[i],nums[i])maxn,minn = max(maxn*nums[i],minn*nums[i],nums[i]), min(maxn*nums[i],minn*nums[i],nums[i])# print dp,maxn,minnreturn dp