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

题目描述:

给定一个长度为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 条评论
登录 后参与评论

相关文章

来自专栏Vamei实验室

Python补充05 字符串格式化 (%操作符)

在许多编程语言中都包含有格式化字符串的功能,比如C和Fortran语言中的格式化输入输出。Python中内置有对字符串进行格式化的操作%。 模板 格式化字符串时...

2139
来自专栏人工智能LeadAI

Python中对字节流/二进制流的操作:struct模块简易使用教程

前言 前段时间使用Python解析IDX文件格式的MNIST数据集,需要对二进制文件进行读取操作,其中我使用的是struct模块。查了网上挺多教程都写的挺好的,...

4555
来自专栏小L的魔法馆

C++继承与多态练习--计算图形面积

4159
来自专栏程序生活

最大连续子序列和

https://blog.csdn.net/bitcarmanlee/article/details/51526010

822
来自专栏一英里广度一英寸深度的学习

Python 传值还是传引用

如果 node =None,相当于node指向一个不可变对象,在调用insert函数时,仅传值。

1683
来自专栏肖洒的博客

刷题问题集合

split()通过指定分隔符对字符串进行切片,如果参数num有指定值,则仅分隔 num 个子字符串. usage; str.split(str=””, num=...

1462
来自专栏Python小屋

Python中lambda表达式的常见用法

非常抱歉,昨天发的代码中有一处小错误,已通过留言的方式进行了纠正,详情请见【详解Python列表推导式】 lambda表达式常用来声明匿名函数,即没有函数名字的...

3329
来自专栏swag code

抽象类与抽象方法

在我们抽象实例对象的时候,有这样一种情况,往上层抽象时就会发现很难描述对象的属性和行为,比如“形状” ,其方法计算面积怎么计算?正方形知道怎么计算,长方形也知道...

743
来自专栏Android自学

java中二分查找(折半查找)的写法

1314
来自专栏软件开发 -- 分享 互助 成长

使用数字进行字符遍历

有些时候使用数字进行遍历,然后将数字转化成需要的进制数,再将进制数对应成需要的字符是一种非常有效的方法。 如: 输入一个正整数X,在下面的等式左边的数字之间添加...

20610

扫码关注云+社区