思路:
1、动态规划
2、因为要考虑负数,所以要多维护一条数组。
# 给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
#
#
#
# 示例 1:
#
# 输入: [2,3,-2,4]
# 输出: 6
# 解释: 子数组 [2,3] 有最大乘积 6。
#
#
# 示例 2:
#
# 输入: [-2,0,-1]
# 输出: 0
# 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
# Related Topics 数组 动态规划
# 👍 709 👎 0
# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
min_list = [0 for x in nums]
for i, v in enumerate(nums):
if i == 0:
min_list[0] = nums[0]
continue
nums[i] = max(v, v * nums[i - 1], v * min_list[i - 1])
min_list[i] = min(v, v * nums[i - 1], v * min_list[i - 1])
return max(nums)
# leetcode submit region end(Prohibit modification and deletion)
s = Solution()
print(s.maxProduct([-2, 0, -1]))
print(s.maxProduct([2, 3, -2, 4]))