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

题目描述:

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

相关文章

来自专栏WD学习记录

牛客网 数组中的逆序对

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的...

1273
来自专栏Vamei实验室

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

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

2349
来自专栏mathor

KMP(4)

1465
来自专栏Jack-Cui

第七天、判断三角形的类型

    根据输入的三角形的三条边判断三角形的类型,并输出它的面积和类型。 C代码: /*第七天、判断三角形的类型*/ #include <stdio.h> ...

2190
来自专栏肖洒的博客

刷题问题集合

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

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

P1062 数列

题目描述 给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是: 1,3,4,9,...

3027
来自专栏CodingToDie

Python学习(三): 列表(list)和流程控制

第3 章 列表(list)和流程控制 Table of Contents 列表 顺序执行 条件判断 循环 小例子 列表 相信大家在其他语言中都使用过 列表,在 ...

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

使用数字进行字符遍历

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

22610
来自专栏swag code

抽象类与抽象方法

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

843
来自专栏程序生活

最大连续子序列和

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

992

扫码关注云+社区

领取腾讯云代金券