N个数的数组求N-1个数组合乘积最大的一组

  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 }