学步园

问题来源：《编程之美》2.13 子数组的最大乘积

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

1. 把所有（N-1）个数的组合找出来，分别计算它们的乘积，并比较大小，由于总共有N个（N-1）个数的组合，总的时间复杂度是O(N^2)，不好。

2. 以空间换时间，计算（N-1）个元素的最大乘积，假定第 i 个元素排除在外，（0<= i <= N-1），那么

p[i] = s[i-1] * t[i+1],

p[i] 表示出去第 i 个元素后的乘积，s[i-1]表示第i个元素前面所有元素的乘积，t[i+1]表示第i个元素后面所有元素的乘积，这样，我们需要从前往后遍历一次数组得到数组s[], 从后往前遍历一次数组得到数组t[], 于是在一个线性时间内就可得到p[], 遍历一次p[]数组就可得到子数组的最大乘积，时间复杂度为O(n).

3. 统计方法，及数组中所有元素的乘积是P，

若P == 0，

则数组中至少包含一个0元素，出去该0元素后所有元素的乘积记为Q，

a,若Q == 0，则数组中包含2个或者2个以上的0元素，无论我们怎么从数组中去（N-1）个元素，子数组的乘积总是0，故子数组的最大乘积是0；

b,若Q > 0，则除去该0元素后的子数组就是子数组的最大乘积；

c,若Q < 0，则表明有奇数个负数，次数无论将0元素来替换数组中的其它任意一个元素得到的乘积总是0，大于Q，故此时子数组的最大乘积是0，子数组中必须包含该0元素；

若P > 0，

a,若数组中存在正元素，则去掉最小的正元素即可；

b,若数组中不存在正元素，则去掉绝对值最大的负元素即可；

若P < 0，

则表明数组中存在奇数个负元素，根据负负得正，去掉绝对值最小的负数即可得到子数组的乘积最大的组合。

程序描述如下：

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

void analyse(int array[], int size)
{
    int zeroNum = 0;
    int negativeNum = 0;
    int positiveNum = 0;
    int maxNegative = INT_MIN;
    int minPositive = INT_MAX;
    int zeroIndex = 0;
    int minNegative = 0;
    for(int i = 0; i < size; ++i) {
        if(array[i] == 0) {
            ++zeroNum;
            zeroIndex = i;
        }
        else if(array[i] < 0) {
            ++negativeNum;
            if(array[i] > maxNegative)
                maxNegative = array[i];
            if(array[i] < minNegative)
                minNegative = array[i];
        }
        else {
            ++positiveNum;
            if(array[i] < minPositive)
                minPositive = array[i];
        }
    }

    //如果数组中包含两个或者两个以上0，那么子数组的乘积肯定为0
    if(zeroNum >= 2) {
        printf("all subArray elements' product is equal to zero");
        return;
    }

    //如果数组中只包含一个0，那么分两个情况：
    //1.去除该0元素其余所有数的乘积为正，那么去除该0元素后所得的子数组乘积最大
    //2.去除该0元素其余所有数的乘积为负，那么子数组最大的乘积为0，子数组中必须包含0元素
    if(zeroNum == 1) {
        if(negativeNum % 2 == 0) {
            printf("the sunArray elements' indexs is except: %d\n", zeroIndex);
        }
        else {
            printf("the subArray must have the index %d of element\n", zeroIndex);
        }

        return;
    }

    //如果数组中有偶数个负数：
    //1.假定数组中存在正元素，则去掉最小正元素即可得到子数组的最大乘积
    //2.假定数组中不存在正元素，则需要去掉最小的负数，即绝对值最大的负数
    //如果数组中有奇数个负数：
    //则只需要去掉值最大的负数，及绝对值最小的负数
    if(negativeNum % 2 == 0 && positiveNum > 0) {  //需考虑没有正元素的情况
        printf("the subArray elements' indexs in except: %d\n", minPositive);
    }
    else if(negativeNum % 2 == 0 && positiveNum == 0) {
        printf("the subArray elements' indexs is except: %d\n", minNegative);
    }
    else {
        printf("the subArray elements' indexs is except: %d\n", maxNegative);
    }

}

int main()
{
    int a[] = {-3, -9, -12, -35, -89, 0};
    analyse(a, sizeof(a)/ sizeof(int));
}