算法题系列之二:求最大子数组之积

题目描述:

给定一个长度为N的整数数组,只允许用乘法,计算任意(N-1)个数的组合中乘积最大的一组。

算法分析:

动态规划的做法,假设数组为a[N],max[N]表示以下标为i结尾的子数组乘积最大值,min[N]表示以下标为i结尾的子数组乘积最小值。为了处理数组元素为负的问题,必须将最小乘积也保存起来。

很容易想到,若当前元素a[i]为负数,那么a[i]*max[i-1]得到的值并不一定比a[i] * min[i-1]大,因为min[i-1]可能为负,如果min[i-1]的绝对值大于max[i-1],那么a[i] * min[i-1]负负相乘的值则更大。因此有以下转移方程

求三者最大

max[i] = MaxinThree(a[i], a[i]*max[i-1], a[i]*min[i-1])

求三者最小

min[i] = MininThree(a[i], a[i]*max[i-1], a[i]*min[i-1])

C#代码实现:

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-08-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏owent

最长单调子序列 复杂度nlog(n)

591
来自专栏Python小屋

Python扩展库numpy中的布尔运算

首先解答上一篇文章Win10系统配置Python3.6+OpenGL环境详细步骤中的问题。该问题的答案为[2, 2],要点在于列表对象的方法index()默认是...

3069
来自专栏数据结构与算法

P1144 最短路计数

题目描述 给出一个N个顶点M条边的无向无权图,顶点编号为1~N。问从顶点1开始,到其他每个点的最短路有几条。 输入输出格式 输入格式: 输入第一行包含2...

33114
来自专栏数据结构与算法

洛谷P3382 【模板】三分法(三分)

960
来自专栏机器学习算法与Python学习

Python: numpy总结(3)

21、dot矩阵点积 例子: ll = [[1,2,3],[4,5,6],[7,8,9]]ld = dot(ll,ll) print 'dot:',l...

3194
来自专栏数据结构与算法

05:最大值和最小值的差

05:最大值和最小值的差 总时间限制:1000ms内存限制:65536kB描述 输出一个整数序列中最大的数和最小的数的差。 输入第一行为M,表示整数个数,整数个...

3295
来自专栏技术小站

c++(三)

函数在调用之前必须进行声明或者定义,函数的声明:返回值类型 函数名(参数类型 参数名称.......);其中参数名称可以省略;

813
来自专栏mathor

Xor(滴滴笔试题)

 给出一个数组,问最多有多少个不重叠的非空区间,使得每个区间内的数字的xor都等于0。

461
来自专栏机器学习算法全栈工程师

最长递增子序列

最长递增序列不要求数组元素连续问题,返回递增序列长度和递增序列。o(n^2)做法,顺序比较以第i个元素开头的递增序列即可。 利用动态规划来做,假设数组为1, -...

3296
来自专栏前端儿

前缀式计算

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是...

711

扫描关注云+社区