给定一个长度为N的整数数组,只允许用乘法,计算任意(N-1)个数的组合乘积中最大的一组。
通过判断数组中0的个数,负数的个数,正数的个数,来求出最大乘积。复杂度为O(N)。
//给定一个长度为N的整数数组,只允许用乘法,计算任意(N-1)个数的组合乘积中最大的一组,并
//写出算法的时间复杂度。
public class MaxMutilCombination {
public static void main(String[] args) {
int[]a={5, 1, 12, -2, 3,-4};
int ex=shouldExculed(a);
for(int i=0;i<a.length;i++){
if(ex==i)continue;
System.out.print(a[i]+" ");
}
}
//返回应该排除的数的序号
public static int shouldExculed(int [] a){
int p,q,r;//p:0的个数 q:负数的个数 r:正数的个数
int i0;//0元素所在的下标
int imin;//最小正数的下标
int mimax,mimin;//最大负数,最小负数的下标
p=q=r=i0=imin=mimax=mimin=0;
for(int i=0;i<a.length;i++){//遍历计算p,q ,r的值,并保存最大值最小值的位置
if(a[i]==0){//0的个数
p++;
i0=i;
}
else if(a[i]<0){//负数的个数
q++;
if(q==1)mimax=mimin=i;
else{
if(a[i]>a[mimax])mimax=i;
if(a[i]<a[mimin])mimin=i;
}
}
else {//正数的个数
r++;
if(r==1)imin=i;
else {
if(a[i]<a[imin])imin=i;
}
}
//1.有两个0时,可以提前结束
if(p==2)return i;//如果有两个0,随便返回一个下标即可,任何组合的积都为0
}
//2.有一个0时
if(p==1){//有一个0,并且奇数个负数时,最大乘积为0,随便去掉一个数即可
return isOdd(q)?mimax:i0;//如果负数的个数为偶数时,则去掉0
}
//3.q=0,全为正数,去掉最小的一个正数即可
if(q==0)return imin;
//4.q为奇数,去掉最大的负数即可,
if(isOdd(q))return mimax;
else if(r>0) return imin;//5.如果正数个数不为0 ,最小的正数
else return mimin;//6.全为负数且是奇数个,去掉最小的负数
}
private static boolean isOdd(int q) {
return 1==(q&0x01);
}
}
分享到:
相关推荐
这个问题要求我们从一个整数数组中找到连续子数组,使得这个子数组的所有元素乘积最大。这个问题不仅出现在面试中,也是数据分析和算法设计的重要实践。 首先,我们需要理解问题的关键点:数组可以包含正数、负数...
在计算机科学领域,特别是算法设计中,“子数组最大乘积”问题是一个经典的动态规划问题。该问题通常表述为:给定一个长度为`N`的整数数组,如何找到一个长度为`N-1`的子数组,使得这些数字的乘积最大?在此问题中,...
为了解决乘积超出数据范围的问题,可以采用数组来存储大整数的方法。具体来说,可以通过一个数组来模拟大整数的存储和计算过程。每个数组元素代表大整数的一位或者几位数字,通过这种方式可以有效地避免数值溢出,...
示例:输入: [1,2,3,4]输出: [24,12,8,6]算法1:暴力法- 不出意料的超时改进思路1:- 除自身以外的乘积 = 自身左边的乘积 * 自身右边
除自身以外数组的乘积 给你一个整数数组 nums,返回数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数...
题目 "乘积最大子数组(动态规划)1" 是一道典型的动态规划问题,来源于 LeetCode 平台。问题要求在给定的整数数组 `nums` 中找出乘积最大的连续子数组,并返回这个子数组的最大乘积。动态规划是一种解决复杂问题的...
# 除自身以外数组的乘积 # 给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output , # 其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 # 输入示例 # [1,2,3,4] # 输出示例 # [24,12,8,6]...
在LeetCode的第152题“乘积最大子数组”中,目标是找到一个整数数组中的连续子数组,使得这个子数组的乘积最大。这个问题可以通过动态规划(Dynamic Programming, DP)来解决,主要考察了数组处理和优化算法的能力。...
这个压缩包特别聚焦于第238题,该题目的目标是计算数组中每个元素除自身以外所有元素的乘积。 题目描述:给定一个整数数组`nums`,你需要找出数组中每个元素除自身以外的乘积。返回一个数组`output`,其中`output[i...
首先,我们要理解问题的核心:给定一个整数数组nums和一个正整数k,我们需要找到数组中乘积最大的k个数。这里的关键点在于,单纯的排序并不能直接解决这个问题,因为乘积的大小受到正负数的影响,而且我们不仅要找出...
numsanswer answer[i]numsnums[i] O(n) 时间复杂度 时间复杂度 时间复杂度 时间复杂度 时间复杂度
最大K乘积问题: 设I是一个n位十进制整数。如果将I划分为k段,则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法,对于给定的I和k,求出I的最大k乘积。 编程任务: 对于给定的I 和k,编程计算I ...
再从右到左遍历一遍,将 nums[i] 右侧的元素乘积累积起来,再乘以原本 res[i] 的值,即为 nums 中除了 nums[i] 之外的其他所有元素乘积。
这个名为"Java-Leetcode-乘积最大子数组.zip"的压缩包很可能包含了某个开发者解决LeetCode上的一道问题——“乘积最大子数组”(Max Product Subarray)的Java实现代码。这道问题是关于数组处理和动态规划的经典实例...
题目 "数组中两元素的最大乘积1" 是一道典型的算法问题,属于计算机科学中的数组处理和最优化问题。这个问题在 LeetCode 上有相应的标签,意味着它可能是 LeetCode 的练习题目。给定一个整数数组 `nums`,目标是找到...
### 乘积最大子数组问题解析 #### 一、问题背景与定义 在处理一系列数值时,经常会遇到求解特定子序列(或子数组)的问题。对于“乘积最大子数组”这一问题,其核心是寻找一个连续子数组,使得该子数组中所有元素...
整个程序完成后,用户可以通过控制台交互输入两个二维数组,程序会自动计算并输出它们的乘积。此算法适用于小规模矩阵,对于大规模矩阵,可以考虑使用更高效的算法,如Strassen分治算法或Coppersmith-Winograd算法。...
算法设计实验-最大k乘积问题 亲自用Dev-C++测试实验结果,没有任何问题!
对于这个问题,我们可以维护两个变量,一个用于跟踪当前子数组的最大乘积,另一个用于跟踪最小乘积。这是因为负数乘以当前的最大乘积可能会变成新的最大乘积,而负数乘以最小乘积则可能变成新的最小乘积。 以下是...