首页 > 代码库 > 子数组的最大乘积

子数组的最大乘积

  这个题目的意思是在一个含有N个数字的数组中,找出N-1个数字,使得这N-1个数字的乘积最大,不允许使用除法。

  一开始看这个题的感觉可能是很简单,我只要找出这个数中最小的值,那么剩余的N-1个数的乘积一定是最大的。

  但是这就忽略了一个情况,就是存在负数的情况。题目中并没有说是个正数的数组。因此在拿到一道题目时,一定要尽可能的想清楚题目的各个方面。

  但是我们依然可以利用上面的这个思路进行查找。首先遍历一遍数组,记录负值绝对值最大和最小的点,0的个数,正数的个数和负数的个数。完成遍历之后,就可以根据以下几种情况进行分析了。

  如果有2个或以上的0,那么结果肯定为0.

  如果只有一个0,如果剩余的数中,负数的个数为奇数,那么乘积最大值一定是0。如果负数的个数是偶数,那么乘积就是这个N-1个数之和。

  如果不含零,负数的个数是奇数,那么去掉负数中绝对值最小的点即可。如果负数的个数是偶数,那么去掉正数中最小的值即可(这里还包含一种特殊情况,就是全是负数,那么就没有正数的最小的值可以去掉,那么就去掉负数中绝对值最大的点)。

  按照以上的步骤进行,只要需要遍历一次数组即可。