LeetCode刷题DAY 20：乘积最大子数组
⭐️⭐️⭐️⭐️
1
题目描述
给定一个整数数组 nums ，找到一个具有最大乘积的连续子数组（子数组最少包含一个元素），返回其最大乘积。如输入[-2,1,-3]返回1。
2
题解
思路：动态规划
本题主要思想与LeetCode刷题DAY 19：最大子序和比较类似，只是在状态转移时要考虑数学计算方面的特殊性。求最大和时，转移的重点是在当前元素上加一个整数，否则只保留自身，求最大乘积时，因为有负负得正的因素，因此要考虑当前元素的符号。如果当前元素是正数，则与一个大数相乘更容易得到一个更大的乘积，如果当前元素是负数，则与一个小数相乘更容易得到一个更大的乘积，所以状态转移时不仅要记录当前元素结尾的最大乘积，还要记录当前元素结尾的最小乘积。
- 第一步，找到中间状态：此处中间状态max_st[i]表示第i个元素结尾的子数组最大乘积，min_st[i]表示第i个元素结尾的子数组最小乘积。
- 第二步，确定状态转移：当nums[i]为正数，则直接与前一步最大乘积和最小乘积相乘，并与自身比较，实现最大值、最小值的状态转移，否则与前一步最大值相乘并与自身比较得到当前最小值乘积，与前一步最小值相乘并与自身比较得到当前最大值。
class Solution: def maxProduct(self, nums: List[int]) -> int: max_st, min_st = [0] * len(nums), [0] * len(nums) max_st[0], min_st[0] = nums[0], nums[0] for i in range(1,len(nums)): if nums[i]>=0: max_st[i] = max(nums[i],nums[i]*max_st[i-1]) min_st[i] = min(nums[i],nums[i]*min_st[i-1]) else: max_st[i] = max(nums[i],nums[i]*min_st[i-1]) min_st[i] = min(nums[i],nums[i]*max_st[i-1]) return max(max_st)本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读