牛客题霸：子数组最大乘积

本文主要是介绍牛客题霸：子数组最大乘积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定一个double类型的数组arr，其中的元素可正可负可0，返回子数组累乘的最大乘积。

示例1

输入

[-2.5,4,0,3,0.5,8,-1]

返回值

12.00000

 

动态规划算法：

一看本题目知识点是动态规划
dp[i] = dp[i-1]的一系列操作
但是发现未果,因为是连续的子树组,所以最小值也可能摇身一变把歌唱,成为最大值
所以可以定义一个imax imin,来分别遍历最大值和最小值.

dp公式:

1 2	imax = max(arr[i]*imax,arr[i]*imin,arr[i]) imin = min(arr[i]*imax,arr[i]*imin,arr[i])

但是最大的坑!这时候第一次计算的时候imax值会更改,所以imin计算的imax,是应该被计算的imax的子imax.

 

解法1：

class Solution:def maxProduct(self , arr ):if arr == []: return 0.0imax ,imin ,res = arr[0], arr[0], arr[0]for i in range(1,len(arr)):imax=  max(arr[i]*imax,arr[i]*imin,arr[i])imin = min(arr[i]*imax,arr[i]*imin,arr[i])res = max(res,imax)return res

 

 

这篇关于牛客题霸：子数组最大乘积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---