子数组最大乘积

[编程题]子数组最大乘积

热度指数：24229 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

数据范围：数组大小满足 $0 \le n \le 10$ ，数组中元素满足 $|val| \le 10$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

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

输出

12.00000

说明

取连续子数组[3,0.5,8]可得累乘的最大乘积为12.00000

示例2

输入

[1.0,0.0,0.0]

输出

1.00000

说明

取连续子数组[1.0]可得累乘的最大乘积为1.00000

算法知识视频讲解

不会做题的小菜鸡

发表于 2021-07-16 00:27:46

精华题解思路此题是一类动态规划问题，具有重叠子问题和最优子结构的特点，通过找到状态转移方程式来解决问题方法一：动态规划我们可以定义一个动态规划数组dp[i]，其表示的是从索引0到索引i位置为止，这一段区间存在的子数组的最大乘积保存在dp[i]中，因此对于一个n长的数组，最终返回结果为max(dp[0 展开全文

ButterFlyEffect

发表于 2020-10-27 13:41:13

又是一个求连续区间数组的问题，典型的动态规划问题。和求最大区间和不同的是，如果我们依然尝试用dp[i]表示以a[i]结尾的子区间的最大成绩。会发现由于负数的存在，会导致乘法结果反转。dp[i-1]a[i]反倒变成了最小值，无法得到状态转移方程。沿着乘法的特性看，如果a[i]为负数，那么dpa[i]时展开全文

Edwin_Xu

发表于 2020-08-28 00:41:53

子数组最大乘积描述: 给定一个double类型的数组arr，其中的元素可正可负可0，返回连续子数组累乘的最大乘积。解法1：暴力求解求子数组的最大乘积，最简单的方式是直接暴力遍历每一个子数组，求得最大的积即可。 Java实现如下： public double maxProduct01(d 展开全文

324134134143428

发表于 2020-09-26 17:47:32

一看本题目知识点是动态规划dp[i] = dp[i-1]的一系列操作但是发现未果,因为是连续的子树组,所以最小值也可能摇身一变把歌唱,成为最大值.所以三十年河东....所以可以定义一个imax imin,来分别遍历最大值和最小值. dp公式: imax = max(arr[i]*imax,a 展开全文