1 /*  2 编程之美题，给定N个数的数组，只能使用乘法，不使用除法，找出N-1个数的乘积最大的一组，有两种方法，方法一：采用两个数组分别保存从左向右  3 和从又向左的两个乘积值，然后在扫描一次，求出最大乘积，空间换时间的方法。  4 方法二：通过分析这些数的性质，看有多少正数，多少负数，多少0  5 （1）如果有2个或2个以上的0，则返回0  6 （2）如果有一个0，则看去除0后的乘积为正数还是负数，如果是负数，最大值为0，返回0（即当有一个0时，看负数奇偶情况，如果负数个数是奇数，则返回0）  7 ，如果是正数，则返回这个正数（即其它所有的乘积）  8 （3）如果总乘积为负数，则根据负负为正，去除绝对值最小的负数  9 （4）如果总乘积为正数，则如果存在正数，则除去绝对值最小的正数，否则除去绝对值最大的负数。 10 因为题目不让用除法，所以不能直接乘出总乘积，然后用除法，所以要一次扫描，记录正数个数，负数个数，绝对值最小正数，绝对值最小的负数，绝对值最大的负数。 11 */ 12  13 #include <iostream> 14 using namespace std; 15  16 double maxmultiply(const double *A,int n) 17 { 18     if(A==NULL) 19         return 0; 20     double * left=new double[n]; 21     double * right=new double[n]; 22     left[0]=A[0]; 23     right[n-1]=A[n-1]; 24     for(int i=1;i<n;i++) 25         left[i]=left[i-1]*A[i]; 26     for(int i=n-2;i>=0;i--) 27         right[i]=right[i+1]*A[i]; 28     double result=A[0]; 29     result=max(left[n-2],right[1]);   //先判断两个边界的时候，后面就不用比较了。 30     for(int i=1;i<=n-2;i++) 31     { 32         result=max(result,left[i-1]*right[i+1]); 33     } 34     return result; 35 } 36  37 /* 38 方法二，记录正负数个数 39 */ 40 double maxmultiply2(const double *A ,int n) 41 { 42     if(A==NULL) 43         return 0; 44     int pos=0; 45     int neg=0; 46     int zero=0; 47     double fabminp=A[0];             //绝对值最小的正数 48     double fabminn=A[0];             //绝对值最小的负数 49     double fabmaxn=A[0];             //绝对值最大的负数 50     double result=1; 51     for(int i=0;i<n;i++) 52     { 53         if(A[i]==0) 54             zero++; 55         if(A[i]>0) 56         { 57             pos++; 58             if(A[i]<fabminp) 59                 fabminp=A[i]; 60         } 61         if(A[i]<0) 62         { 63             neg++; 64             if(A[i]*(-1)<fabminn) 65             { 66                 fabminn=A[i]; 67             } 68             if(A[i]*(-1)>fabmaxn) 69             { 70                 fabmaxn=A[i]; 71             } 72         } 73     } 74     if(zero>=1) 75     { 76         if(zero>=2)                              //有两个以上0，返回0. 77             return 0; 78         else if((neg&1)==0)                        //有一个0，并且负数个数是偶数，说明乘积为正数，返回该正数，必须加括号才行 79         { 80             for(int i=0;i<n;i++) 81             { 82                 if(A[i]!=0) 83                     result*=A[i]; 84             } 85             return result; 86         } 87         else   return 0;                         //有一个0，并且其余乘积为负数，最大为0. 88     } 89     else if((neg&1)==0)                           //负数个数是偶数(包括0)，则总乘积为正,必须加括号才行 90     { 91         if(pos>0)                                       //如果有正数，则去除最小正数，例如2,3,4，-1，-2，去除2，如果3，-1，-2，则除去3 92         { 93             for(int i=0;i<n;i++) 94             { 95                 if(A[i]!=fabminp) 96                     result*=A[i]; 97             } 98             return result; 99         }100         else                                  //没有正数情况，是偶数个负数，例如-2，-3，-4，-5,去除绝对值最大的负数                                  101         {102             for(int i=0;i<n;i++)103             {104                 if(A[i]!=fabmaxn)105                     result*=A[i];106             }107             return result;108         }109     }110     else                                       //负数个数是奇数个，总乘积为负数例如2,3，-1，-2，-3，此时去除绝对值最小的负数，-1                      111     {112         for(int i=0;i<n;i++)113         {114             if(A[i]!=fabminn)115                 result*=A[i];116         }117         return result;118     }119 }120 121 122 int main()123 {124     double A[]={2,9,-1,3,7,0,8,9,-3};125     int n=9;126     cout<<maxmultiply2(A,n)<<endl;127     system("pause");128 }