题解 | #连续子数组的最大乘积#
连续子数组的最大乘积
https://www.nowcoder.com/practice/fd8c819c07c9493887bfac8549c119f4
思路：动态规划
和上一题的最大子数组和不同的是，这题为最大乘积，所以要额外保存每次的一个最小值，规避负负得正的情况。
1. 确定dp数组代表的含义
dp_max[i]：以下标 i 结尾的连续子数组的最大乘积
dp_min[i]：以下标 i 结尾的连续子数组的最小乘积，保留最小负值
2. 确定递推公式
dp_max[i] = max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
dp_min[i] = min(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
dp_min[i] = min(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
3. 初始化
dp_max初始化为最小值 -inf，dp_min初始化为最大值 inf
dp_max[0] = nums[0]
dp_min[0] = nums[0]
代码：
n = int(input())
nums = list(map(int, input().split()))
dp_max = [float('-inf')] * n
dp_min = [float('inf')] * n
dp_max[0] = dp_min[0] = nums[0]
for i in range(1, n):
dp_max[i] = max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
dp_min[i] = min(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
print(max(max(dp_max), max(dp_min)))
查看14道真题和解析
小红书公司福利 950人发布