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

题目描述:

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

相关文章

来自专栏WOLFRAM

错觉艺术的巅峰,错觉图形大师M.C. Escher的不可能方块的可能模型

1333
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2272
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

5896
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1272
来自专栏Petrichor的专栏

Dataset 列表:机器学习研究

In computer vision, face images have been used extensively to develop face recog...

1481
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9744
来自专栏技术之路

wpf键盘记录器

很简单的一个wpf键盘记录器 ? 这个程序我一样用了全局勾子,之前用的都是winform上运行了,前一段时间 在国外的论坛上逛看到了一个wpf能用的就做了一个小...

2005
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1142
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2169

扫码关注云+社区