本文主要是介绍第二十八章续：任意（N-1）个数的组合中乘积最大的一组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意（N-1）个数的组合中乘积最大的一组，并写出算法的时间复杂度。
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std; /*
给定一个长度为N的整数数组，只允许用乘法，不能用除法，
计算任意（N-1）个数的组合中乘积最大的一组，并写出算法的时间复杂度。
*/
/*方法1：
s[i]表示0到i-1乘积，t[i]表示i+1到n乘积，有Max={s[i]*t[i]}
*/
long caculate(int arr[],int length){long maxV=LONG_MIN;long *s=new long[length+1];long *t=new long[length+1];s[0]=1,t[length-1]=1;for(int i=1;i<=length;++i)s[i]=s[i-1]*arr[i-1];for(int i=length-2;i>=0;--i){t[i]=t[i+1]*arr[i+1];}for(int i=0;i<length;++i)maxV=max(maxV,s[i]*t[i]);delete[] s;delete[] t;return maxV;
}
/*方法2：
统计数组中正负零的个数
*/
long caculate2(int arr[],int length){long multi=1;//结果bool flag=false;//标识，数组中去掉的只能是一个数int opt=0,neg=0,zero=0;//正负零的个数int minO=INT_MAX,maxN=INT_MIN;//最小的正数和最大的负数for(int i=0;i<length;i++){if(arr[i]<0){neg++;maxN=max(maxN,arr[i]);}else if(arr[i]>0){opt++;minO=min(minO,arr[i]);}else zero++;}if(zero>1)return 0;//1个0的情况if(zero==1){if(neg&1)return 0;//奇数个负数else{for(int i=0;i<length;++i)if(arr[i]!=0)multi*=arr[i];return multi;}}//有奇数个负数，去掉最大的负数，即绝对值最小的负数if(neg&1){for(int i=0;i<length;++i){if(arr[i]!=maxN||flag){multi*=arr[i];}else flag=true;}return multi;}//有偶数个负数，去掉最小的正数for(int i=0;i<length;++i){if(arr[i]!=minO||flag){multi*=arr[i];}else flag=true;}return multi;
}
int main()
{ int arr[]={-2,0,-3,-4,5,6,-1,-3};cout<<caculate2(arr,8);
} 这篇关于第二十八章续：任意（N-1）个数的组合中乘积最大的一组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
