编程之美系列之求子数组的最大乘积

题目描述：给定一个长度为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));
}
}

补充：软件开发 , C++ ,