首页 > 代码库 > 编程之美----子数组的最大乘积
编程之美----子数组的最大乘积
问题:给定一个长度为N的整数数组,只允许用乘法,不能用除法,计算任意(N-1)个数的组合中乘积最大的一组,并写出算法的时间复杂度。
解法一:用一个数组保存从左边到右边前i个元素的乘积。用另一个数组保存从右边到左边N-i个元素的乘积。然后结果就为两个数组中元素对应的乘积,复杂度为o(N)。
解法二:设N个数的乘积为P,对P进行分析。
1,P为0,则数组中至少包含一个0,假设除去一个0后,其它N-1个数的乘积为Q,若Q为0,则数组中至少有两个0,则返回0.若Q为正数,返回Q。若Q为负数,返回0.
2,P为负数。扫描一遍数组,去掉绝对值最小的负数。
3,P为正数。若数组中存在正数值,那么去掉最小的正数值,否则去掉绝对值最大的负数值。
对于P的正负性判定,可不需要直接求乘积,而是扫描一遍数组,求出数组中正数、负数、和0的个数,从而判断P的正负性,遍历的同时求出绝对值最小的正数和负数,绝对值最大的正数和负数,复杂度为o(N).
编程之美----子数组的最大乘积
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。