Maximum Product
DP; Medium
1. Link
2. 题目描述
给定一个double类型的数组arr,其中的元素可正可负可0,返回子数组累乘的最大乘积。示例1
输入
复制
[-2.5,4,0,3,0.5,8,-1]
返回值
复制
12.00000
3. 思路
DP
state: max_dp[i] ,min_dp[i] 以当前第i个位置为结尾的连续的乘积的的最大和最小值, 这个i一般是指上一次的结果不包含这次的arr[i]
因为有可能负负得正得到最大值,所以要保留负数最小值
每次从max_dp arr[i], min_dparr[i], arr[i] 里面取最大和最小更新
当前最大值和最小值, 那么其中最大值或最小值肯定有一个是乘上arr[i]或者reset成为arr[i], 这样下次乘上下一个arr[i+1]时乘积始终是连续的
case 1: 前面累乘的值是 和当前值是同号
case 2: 前面累乘的值和当前的值是异号
我们希望正值和负值的绝对值越乘越大,使得下一次再遇到负值的时候可以把当前累乘最小的负值变成正值,所以需要 max(max_valarr[i], min_val arr[i], arr[i]),
和arr[i]对比是为了考虑到前面累乘的数字是小数,结果绝对值越乘越小 比 arr[i]的绝对值还小的情况。
class Solution:
def maxProduct(self , arr ):
# state: max_dp[i] ,min_dp[i]上次状态的最大和最小值
# transition function:
#max_dp_new = max(max_dp* arr[i] , min_dp *arr[i], arr[i])
#min_dp_new = min(max_dp* arr[i] , min_dp *arr[i], arr[i])
# 1. 因为有可能负负得正得到最大值,所以要保留负数最小值
#2. 每次从max_dp *arr[i], min_dp*arr[i], arr[i] 里面取最大和最小更新
#当前最大值和最小值, 那么其中最大值或最小值肯定有一个是乘上arr[i]或者reset成为
# arr[i], 这样下次乘上下一个arr[i+1]时乘积始终是连续的
#
#
if not arr:
return None
res = max_dp = min_dp = arr[0]
for i in range(1, len(arr)):
max_dp_new = max(max_dp* arr[i] , min_dp *arr[i], arr[i])
min_dp_new = min(max_dp* arr[i] , min_dp *arr[i], arr[i])
max_dp = max_dp_new
min_dp = min_dp_new
res = max(res, max_dp)
return res
Last updated
Was this helpful?