怎样做免费网站的推广,网站开发好找工作吗,大良建网站,淘宝客网站需要备案问题#xff1a;给定一个长度为N的整数数组#xff0c;只允许用乘法#xff0c;不能用除法#xff0c;计算任意(N-1)个数的组合中乘积最大的一组#xff0c;并写出算法的时间复杂度。 解法一#xff1a;用一个数组保存从左边到右边前i个元素的乘积。用另一个数组保存从右…问题给定一个长度为N的整数数组只允许用乘法不能用除法计算任意(N-1)个数的组合中乘积最大的一组并写出算法的时间复杂度。 解法一用一个数组保存从左边到右边前i个元素的乘积。用另一个数组保存从右边到左边N-i个元素的乘积。然后结果就为两个数组中元素对应的乘积复杂度为o(N)。 解法二设N个数的乘积为P对P进行分析。 1P为0则数组中至少包含一个0假设除去一个0后其它N-1个数的乘积为Q若Q为0则数组中至少有两个0则返回0.若Q为正数返回Q。若Q为负数返回0. 2P为负数。扫描一遍数组去掉绝对值最小的负数。 3P为正数。若数组中存在正数值那么去掉最小的正数值否则去掉绝对值最大的负数值。 对于P的正负性判定可不需要直接求乘积而是扫描一遍数组求出数组中正数、负数、和0的个数从而判断P的正负性遍历的同时求出绝对值最小的正数和负数绝对值最大的正数和负数复杂度为o(N).转载于:https://www.cnblogs.com/wen-ge/p/4127150.html