題目描述：給定一個長度為N的整數數組，只允許用乘法，計算任意（N-1）個數的組合中乘積最大的一組，並寫出算法的時間復雜度。
算法分析：
1、二逼青年的做法，把所有可能的（N-1）個數的組合照出來，分別計算它們的乘積，並比較大小。好吧~時間復雜度是O(N^2)，這種效率，我連代碼都懶得寫。
2、來點文藝一點的，其實也就是上個月去參加騰訊筆試的一道附加題，我當時就做出來了。具體的看另外一篇博客：面試100題系列之3關於一種拆分思路的算法，這裡就不廢話了，碼字也很辛苦的說~~~
3、從數學的角度來分析一下。要求的是最大值，而且需要抽取N-1個數，也就是捨棄一個數呗~與其去找需要的N-1個數，還不如去確定需要捨棄的數。怎麼確定呢？
*如果0的個數超過2個，那不管捨棄什麼數，剩下的至少有一個0，那結果肯定是0啦。
*如果只有1個0呢？如果負數個數為奇數，那捨棄0的話肯定就得到一個負數，那還不如得到0呢！也就是說這種情況隨便捨棄一個不為0的數就可以了。如果負數的個數是偶數，把0捨棄就可以了。
*如果沒有0，那就好辦了。負數個數為奇數，捨棄絕對值最小的負數。否則捨棄絕對值最大的正數就可以了。
當然所有的關於上面的信息都可以在遍歷一次數組後得到。知道需要捨棄哪一個之後，重新遍歷一遍數組，乘的時候跳過那個元素就可以了。核心代碼如下：
[cpp]
double GetMaxProduct(double *arr, int nLen)
{
if(!arr || nLen < 1)
return -Inf;
int i;
int NagCnt,PosCnt,ZeroCnt;
NagCnt = PosCnt = ZeroCnt = 0;
double MaxNag, MinPos;
MaxNag = -Inf;
MinPos = Inf;
for(i = 0; i < nLen; ++i)
{
if(arr[i] < -Bound)
{
++NagCnt;
MaxNag = max(MaxNag, arr[i]);
}
else if(arr[i] > Bound)
{
++PosCnt;
MinPos = min(MinPos, arr[i]);
}
else
{
++ZeroCnt;
if(ZeroCnt >= 2)//0多於2個
return 0.0;
}
}
//1個0，奇數個負數
if(ZeroCnt && (NagCnt & 1))
return 0.0;
//確定需要去除的元素
double except;
if(NagCnt & 1)
except = MaxNag;
else
except = ZeroCnt ? 0.0 : MinPos;
MinPos = 1;//重復利用變量Minpos來存放ans
for(i = 0; i < nLen; ++i)
{
if(arr[i] < except + Bound && arr[i] > except - Bound)
continue;
MinPos *= arr[i];
}
return MinPos;
}
double GetMaxProduct(double *arr, int nLen)
{
if(!arr || nLen < 1)
return -Inf;
int i;
int NagCnt,PosCnt,ZeroCnt;
NagCnt = PosCnt = ZeroCnt = 0;
double MaxNag, MinPos;
MaxNag = -Inf;
MinPos = Inf;
for(i = 0; i < nLen; ++i)
{
if(arr[i] < -Bound)
{
++NagCnt;
MaxNag = max(MaxNag, arr[i]);
}
else if(arr[i] > Bound)
{
++PosCnt;
MinPos = min(MinPos, arr[i]);
}
else
{
++ZeroCnt;
if(ZeroCnt >= 2)//0多於2個
return 0.0;
}
}
//1個0，奇數個負數
if(ZeroCnt && (NagCnt & 1))
return 0.0;
//確定需要去除的元素
double except;
if(NagCnt & 1)
except = MaxNag;
else
except = ZeroCnt ? 0.0 : MinPos;
MinPos = 1;//重復利用變量Minpos來存放ans
for(i = 0; i < nLen; ++i)
{
if(arr[i] < except + Bound && arr[i] > except - Bound)
continue;
MinPos *= arr[i];
}
return MinPos;
}下面給出一些輔助函數和變量的定義，以及main函數的調用，不需要的可以pass了：
[cpp]
#include<stdio.h>
const double Inf = 1e5;
const double Bound = 1e-6;
inline double min(const double a, const double b)
{
return a < b ? a : b;
}
inline double max(const double a, const double b)
{
return a > b ? a : b;
}
int main()
{
const int N = 30;
double arr[N];
int n,i;
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; ++i)
scanf("%lf", &arr[i]);
printf("%lf\n", GetMaxProduct(arr, n));
}
}
#include<stdio.h>
const double Inf = 1e5;
const double Bound = 1e-6;
inline double min(const double a, const double b)
{
return a < b ? a : b;
}
inline double max(const double a, const double b)
{
return a > b ? a : b;
}
int main()
{
const int N = 30;
double arr[N];
int n,i;
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; ++i)
scanf("%lf", &arr[i]);
printf("%lf\n", GetMaxProduct(arr, n));
}
}
