首页 > 代码库 > 编程之美2.13 子数组的最大乘积
编程之美2.13 子数组的最大乘积
这道题目是求 n-1 个数的最大乘积,即数组大小为 n,则会存在 n 个 n-1 的连续数字,那么,我们需要寻找的是最大的那一个乘积。
其实看到题目,感觉很简单,循环走两遍数组就可以得到结果,但是,那样的话,复杂度是平方量级的,如果一个数组中元素很多,那么,时间效率上是不能接受的,所以,需要重新思考问题,寻找简洁的解法。
这里,我们可以利用辅助数组的办法,把需要乘在一起的数字保存下来,单独的放到数组中,然后乘在一块就可以了,这样说起来其实不是那么容易理解,我还是贴出代码吧,里面会有注释,看完代码也就清晰了:
函数声明:
/*2.13 子数组的最大乘积*/ ll DutMaxMultipleInArray(int*, int);
源代码:
/*任意n - 1个数的组合中乘积最大的一组*/ bool _DutMaxMultipleInArray = false; ll DutMaxMultipleInArray(int* A, int size) { if (!A || size <= 0) { _DutMaxMultipleInArray = true; return -1; } /*两个辅助数组,数组元素存储1 -- n - 1个数的乘积*/ ll* s = new ll[size]; ll* t = new ll[size]; ll maxValue = http://www.mamicode.com/1 << 31;>编程之美2.13 子数组的最大乘积
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。