首页 > 代码库 > 子数组的最大乘积
子数组的最大乘积
问题描述:给定一个长度为N的整数数组,只允许用乘法,不能用除法,计算任意(N-1)个数的组合乘积中最大的一组,并写出算法的时间复杂度。
问题分析:先来分析数组的正负情况
1、如果数组中至少有两个是0,那么子数组的最大乘积必为0
2、如果数组中包含一个0,分情况讨论
(1)、如果数组中有偶数个负数,那么他的乘积为除了0以外N-1个数的乘积
(2)、如果数组中有奇数个负数,那么子数组的最大乘积为0
3、如果数组中没有0,分情况讨论
(1)、如果数组中有偶数个负数,那么除了最小正数以外的N-1个数的乘积为最大乘积
(2)、如果数组中有奇数个负数,那么除了绝对值最小的负数以外的N-1个数的乘积为最大乘积
代码:
子数组的最大乘积
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。