首页 > 代码库 > 【编程之美】2.13 子数组的最大乘积
【编程之美】2.13 子数组的最大乘积
题目:一个有N个数的整数数组 取其中N-1个元素的子数组 求子数组的最大乘积 不能用除法。
这道题自己没有写对,没有考虑到负数的情况,只是单纯的想去掉最小的数。 但是若有负数 -5 -4 -3 中-5 * -4 = 20更大。
需要先统计正数、负数和0的个数,再分类讨论。考察的其实就是细心和耐心。
//答案解法int getMaxProductAnswer(int * a, int alen){ int NumPositive = 0; int NumNegtive = 0; int NumZero = 0; int exceptLoction = 0; //去掉的数字的位置 int maxProduct = 1; for(int i = 0; i < alen; i++) { if(a[i] == 0) { NumZero++; } else if(a[i] > 0) { NumPositive++; } else { NumNegtive++; } } if(NumZero >= 2) { maxProduct = 0; } else if(NumZero == 1) { if(NumNegtive & 0x01 == 1) //奇数个负数 { return 0; } else //偶数个负数 去掉0 { for(int i = 0; i < alen; i++) { if(a[i] != 0) { maxProduct *= a[i]; } } } } else { if(NumNegtive & 0x01 == 1) //奇数个负数 去掉负数中绝对值最小的 { int minAbsNegtive = 0; int i = 0; for(i = 0; i < alen; i++) { if(a[i] < 0) { minAbsNegtive = a[i]; exceptLoction = i; break; } } for( ;i < alen; i++) { if(a[i] < 0 && a[i] > minAbsNegtive) { minAbsNegtive = a[i]; exceptLoction = i; } } for(i = 0; i < alen; i++) { if(i != exceptLoction) { maxProduct *= a[i]; } } } else //偶数个负数 { if(NumPositive > 0) //有正数 去掉正数中最小的 { int minPositive = 0; int i = 0; for(i = 0; i < alen; i++) { if(a[i] > 0) { minPositive = a[i]; exceptLoction = i; break; } } for( ;i < alen; i++) { if(a[i] > 0 && a[i] < minPositive) { minPositive = a[i]; exceptLoction = i; } } for(i = 0; i < alen; i++) { if(i != exceptLoction) { maxProduct *= a[i]; } } } else //没有正数 去掉负数绝对值最大的 { int maxAbsNegtive = 0; int i = 0; for(i = 0; i < alen; i++) { if(a[i] < 0) { maxAbsNegtive = a[i]; exceptLoction = i; break; } } for( ;i < alen; i++) { if(a[i] < 0 && a[i] < maxAbsNegtive) { maxAbsNegtive = a[i]; exceptLoction = i; } } for(i = 0; i < alen; i++) { if(i != exceptLoction) { maxProduct *= a[i]; } } } } } return maxProduct;}int main(){ int a[10] = {-2,-4,-6,0,-9,-2,-4,-6,-7,-4}; int maxProduct = getMaxProductAnswer(a, 10); return 0;}
【编程之美】2.13 子数组的最大乘积
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。