子数组的最大乘积

问题描述：给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意（N-1）个数的组合中乘积最大的一组，并写出算法的时间复杂度。

分析与解答：
这里用的是书中给出的方法，统计正数，负数和零的个数，然后对其求解。
假设扫描完一遍数组后，已经统计出正数、负数和零的个数，那么就会是如下几种情况：
1.数组中存在0
   1）数组中存在2个以上的0
        那么，任意（N-1）个数中肯定会有0，此时乘积也为0，直接返回0。
  2）数组中只有一个0
      如果负数的个数为奇数，除去0后的子数组乘积肯定为负数，而含
      有0的子数组乘积为0，故可以直接返回0.
      如果负数的个数为偶数，那么除去0的子数组乘积最大
2.数组中不存在0
  1）负数的个数是奇数
     那么，除去绝对值最小的负数的子数组乘积最大。
  2）负数的个数是偶数
     如果没有正数，此时除去绝对值最大的负数的子数组乘积最大。
     否则，除去正数最小的子数组乘积最大。
代码如下：

#include <stdio.h>
#include <limits.h>

#define MINNUM INT_MIN
#define MAXNUM INT_MAX

int max_multiply(int *a, int n)
{
    int positives = 0;
    int negitives = 0;
    int zeros = 0;
    int minp;
    int maxn, minn;
    int i;
    int not_use;
    int sum = 1;
    int del = 0;
    minp = MAXNUM;
    maxn = MINNUM;
    minn = 0;

    //统计0的个数
    //负数的个数，负数的最小值，最大值
    //正数的个数，正数的最小值，最大值
    for (i=0; i<n; i++)
    {
        if (a[i] > 0)
        {
            positives++;
            if (a[i] < minp)
                minp = a[i];
        }
        else if (a[i] < 0)
        {
            negitives++;
            if (a[i] > maxn)
                maxn = a[i];
            if (a[i] < minn)
                minn = a[i];
        }
        else if (a[i] == 0)
        {
            zeros++;
        }
    }

    //如果有0的存在
    if (zeros != 0)
    {


        //并且0的个数不止1个，返回0
        if (zeros > 1)
            return 0;
        //只有一个0
        else
        {
            //负数为奇数个，直接返回0
            if (negitives&0x1)
                return 0;
            else//除去0
                not_use = 0;
        }
    }
    //没有0
    else
    {
        //负数的个数是奇数，除去负数的最大值
        if (negitives&0x1)
            not_use = maxn;
        //负数的个数是偶数，如果有正数，去除一个正数最小值，否则，去除一个负数最小值
        else
        {
            if (positives > 0)
                not_use = minp;
            else
                not_use = minn;
        }
    }
    for (i=0; i<n; i++)
    {
        if ( (a[i] == not_use) && (!del) )
        {
            del = 1;
            continue;
        }
        sum *= a[i];
    }
    return sum;
}

int main()
{
    int a[] = {-1, -5, -3, 1, 3, 0, 0, 2, 4, 2};
    printf("%d\n", max_multiply(a, 10));
    return 0;
}

这里只需要简单的扫描2次数组即可，所以，复杂度为O(N)