首页 > 代码库 > 【编程之美】2.13 子数组的最大乘积

【编程之美】2.13 子数组的最大乘积

题目:一个有N个数的整数数组 取其中N-1个元素的子数组 求子数组的最大乘积 不能用除法。

 

这道题自己没有写对,没有考虑到负数的情况,只是单纯的想去掉最小的数。 但是若有负数 -5 -4 -3 中-5 * -4 = 20更大。

需要先统计正数、负数和0的个数,再分类讨论。考察的其实就是细心和耐心。

//答案解法int getMaxProductAnswer(int * a, int alen){    int NumPositive = 0;    int NumNegtive = 0;    int NumZero = 0;    int exceptLoction = 0; //去掉的数字的位置    int maxProduct = 1;    for(int i = 0; i < alen; i++)    {        if(a[i] == 0)        {            NumZero++;        }        else if(a[i] > 0)        {            NumPositive++;        }        else        {            NumNegtive++;        }    }    if(NumZero >= 2)    {        maxProduct = 0;    }    else if(NumZero == 1)    {        if(NumNegtive & 0x01 == 1) //奇数个负数        {            return 0;        }        else //偶数个负数 去掉0        {            for(int i = 0; i < alen; i++)            {                if(a[i] != 0)                {                    maxProduct *= a[i];                }            }        }    }    else    {        if(NumNegtive & 0x01 == 1) //奇数个负数 去掉负数中绝对值最小的        {            int minAbsNegtive = 0;            int i = 0;            for(i = 0; i < alen; i++)            {                if(a[i] < 0)                {                    minAbsNegtive = a[i];                    exceptLoction = i;                    break;                }            }            for( ;i < alen; i++)            {                if(a[i] < 0 && a[i] > minAbsNegtive)                {                    minAbsNegtive = a[i];                    exceptLoction = i;                }            }            for(i = 0; i < alen; i++)            {                if(i != exceptLoction)                {                    maxProduct *= a[i];                }            }        }        else //偶数个负数        {            if(NumPositive > 0) //有正数 去掉正数中最小的            {                int minPositive = 0;                int i = 0;                for(i = 0; i < alen; i++)                {                    if(a[i] > 0)                    {                        minPositive = a[i];                        exceptLoction = i;                        break;                    }                }                for( ;i < alen; i++)                {                    if(a[i] > 0 && a[i] < minPositive)                    {                        minPositive = a[i];                        exceptLoction = i;                    }                }                for(i = 0; i < alen; i++)                {                    if(i != exceptLoction)                    {                        maxProduct *= a[i];                    }                }            }            else //没有正数 去掉负数绝对值最大的            {                int maxAbsNegtive = 0;                int i = 0;                for(i = 0; i < alen; i++)                {                    if(a[i] < 0)                    {                        maxAbsNegtive = a[i];                        exceptLoction = i;                        break;                    }                }                for( ;i < alen; i++)                {                    if(a[i] < 0 && a[i] < maxAbsNegtive)                    {                        maxAbsNegtive = a[i];                        exceptLoction = i;                    }                }                for(i = 0; i < alen; i++)                {                    if(i != exceptLoction)                    {                        maxProduct *= a[i];                    }                }            }        }    }    return maxProduct;}int main(){    int a[10] = {-2,-4,-6,0,-9,-2,-4,-6,-7,-4};    int maxProduct = getMaxProductAnswer(a, 10);    return 0;}

 

【编程之美】2.13 子数组的最大乘积