面试题：编程之美：长度为n的整形数组,找出其中的任意n-1个数乘积最大的那一组
一 题目：
即给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意（N-1）个数的组合中乘积最大的一组，并写出算法的时间复杂度。
我们可以把所有可能的（N-1）个数的组合找出来，分别计算它们的乘积，并比较大小。由于总共有N个（N-1）个数的组合，总的时间复杂度为O（N2），显然这不是最好的解法。
二 分析
这是一道老题了，网上搜了下06年了就有了。很惭愧自己还不会。
OK，以下解答来自编程之美：
这个拆分成前后两端算法，还是有些复杂，看到大神有个更简化的思路：
此外，还可以通过分析，进一步减少解答问题的计算量。假设N个整数的乘积为P，针对P的正负性进行如下分析（其中，AN-1表示N-1个数的组合，PN-1表示N-1个数的组合的乘积）。
1.P为0
那么，数组中至少包含有一个0。假设除去一个0之外，其他N-1个数的乘积为Q，根据Q的正负性进行讨论：
Q为0
说明数组中至少有两个0，那么N-1个数的乘积只能为0，返回0；
Q为正数
返回Q，因为如果以0替换此时AN-1中的任一个数，所得到的PN-1为0，必然小于Q；
Q为负数
如果以0替换此时AN-1中的任一个数，所得到的PN-1为0，大于Q，乘积最大值为0。
2. P为负数
根据“负负得正”的乘法性质，自然想到从N个整数中去掉一个负数，使得PN-1为一个正数。而要使这个正数最大，这个被去掉的负数的绝对值必须是数组中最小的。我们只需要扫描一遍数组，把绝对值最小的负数给去掉就可以了。
3. P为正数
类似地，如果数组中存在正数值，那么应该去掉最小的正数值，否则去掉绝对值最大的负数值。
上面的解法采用了直接求N个整数的乘积P，进而判断P的正负性的办法，但是直接求乘积在编译环境下往往会有溢出的危险（这也就是本题要求不使用除法的潜在用意），事实上可做一个小的转变，不需要直接求乘积，而是求出数组中正数（+）、负数（-）和0的个数，从而判断P的正负性，其余部分与以上面的解法相同。
在时间复杂度方面，由于只需要遍历数组一次，在遍历数组的同时就可得到数组中正数（+）、负数（-）和0的个数，以及数组中绝对值最小的正数和负数，时间复杂度为O（N）。
————————————————
版权声明：本文为CSDN博主「v_JULY_v」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/v_july_v/article/details/7974418
附下相关链接：
这事06年的讨论帖子。
https://bbs.csdn.net/topics/90460367
这是使用动态规划解法：