首页 > 代码库 > 子数组的最大乘积
子数组的最大乘积
这个题目的意思是在一个含有N个数字的数组中,找出N-1个数字,使得这N-1个数字的乘积最大,不允许使用除法。
一开始看这个题的感觉可能是很简单,我只要找出这个数中最小的值,那么剩余的N-1个数的乘积一定是最大的。
但是这就忽略了一个情况,就是存在负数的情况。题目中并没有说是个正数的数组。因此在拿到一道题目时,一定要尽可能的想清楚题目的各个方面。
但是我们依然可以利用上面的这个思路进行查找。首先遍历一遍数组,记录负值绝对值最大和最小的点,0的个数,正数的个数和负数的个数。完成遍历之后,就可以根据以下几种情况进行分析了。
如果有2个或以上的0,那么结果肯定为0.
如果只有一个0,如果剩余的数中,负数的个数为奇数,那么乘积最大值一定是0。如果负数的个数是偶数,那么乘积就是这个N-1个数之和。
如果不含零,负数的个数是奇数,那么去掉负数中绝对值最小的点即可。如果负数的个数是偶数,那么去掉正数中最小的值即可(这里还包含一种特殊情况,就是全是负数,那么就没有正数的最小的值可以去掉,那么就去掉负数中绝对值最大的点)。
按照以上的步骤进行,只要需要遍历一次数组即可。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。