首页 > 代码库 > 编程之美----子数组的最大乘积

编程之美----子数组的最大乘积

问题:给定一个长度为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).

编程之美----子数组的最大乘积