N个整数，求其中任意N-1个数的乘积中的最大的一个。
N个整数，求其中任意N-1个数的乘积中的最大的一个。
例如 3,2,1,则最大的是3*2=6
提示：整数包括0和负数
要求给出个比较有效率的算法
我的函数实现：
long GetMaxValueInCumulation(long plIntegerNumbers[],long lIntegerNumbersCount)
{
long lMinIntegerNumber = 1<<sizeof(long);
//不合法输入返回最大的整数
if(!plIntegerNumbers || lIntegerNumbersCount <= 0)
return (lMinIntegerNumber);
long lReturnValue = 1;
long lMaxNegativeValue = 0;
long lNegativeValueCount = 0;
long lIndex = 0;
//中间处理变量
long lCumulationDataIndex = 0;
long plCumulationData = new long[lIntegerNumbersCount];
if(!plCumulationData)
return (lMinIntegerNumber);
memset(plCumulationData,0,lIntegerNumbersCount];
//去掉最小值及0值及处理负数的情况
for(lIndex = 0; lIndex < lIntegerNumbersCount;lIndex++)
{
if( plIntegerNumber[lIndex] > 0 && plIntegerNumbers[lIndex] < lMinIntegerNumber )
lMinIntegerNumber = plIntegerNumbers[lIndex];
if( plIntegerNumbers[lIndex] < 0 )
lNegativeValueCount++;
if(plIntegerNumbers[lIndex] < 0 && lMaxNegativeValue < plIntegerNumbers[lIndex] )
lMaxNegativeValue = plIntegerNumbers[lIndex];
if(plIntegerNumber[lIndex])
plCumulationData[lCumulationDataIndex++] = plIntegerNumber[lIndex];
}
//计算结果
if(lNegativeValueCount < 1)
{
for(lIndex = lCumulationDataIndex - 1;lIndex >= 0;lIndex--)
lReturnValue *= plCumulationData[lIndex];
}
else
{
if(lNegativeValueCount % 2 )
{
for(lIndex = lCumulationDataIndex - 1;lIndex >= 0;lIndex--)
{
if(lMaxNegativeValue == plCumulationData[lIndex] )
continue;
lReturnValue *= plCumulationData[lIndex];
}
}
else
for(lIndex = lCumulationDataIndex - 1;lIndex >= 0;lIndex--)
lReturnValue *= plCumulationData[lIndex];
}
delete []plCumulationData;
return (lReturnValue);
}
学习学习别人更好的办法：）
问题点数：20、回复次数：30Top
1 楼oracleot（如风随影）回复于 2006-12-03 15:30:33 得分 0
我和想法是,先算出所有数的乘积,然后对每个数除一下,选出最大的那个就行了,复杂度为O(n)
计算 S=a1*a2*....*an; 需时O(n)
计算 S1 = S/a1, S2 = S/a2,..... Sn = S/an;(其中,要当心除数为0),需时O(n)
总的复杂度为O(n)Top
2 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-12-03 15:57:47 得分 5
该问题等价于：从 N 个整数中剔除一个，使余下的数乘积最大。
令这N个数依次为 a1,a2,...,an，P=a1*a2*...*an，
(1) 如果 P<0，则剔除其中最大的负整数即可；
(2) 如果 P=0，
2.1 若这 N 个数中有且仅有一个为“0”。若其它数之积为正，则剔除“0”；否则剔除任意一个非零数；
2.2 若这 N 个数中至少有两个为“0”，则随便剔除一个均可；
(3) 如果 P>0，则剔除其中最小的正整数即可。Top
3 楼healer_kx（甘草(楼主揭贴吧，我们这些上班灌水的也不容易)）回复于 2006-12-03 15:58:30 得分 10
int main(int argc, char* argv[])
{
int a[] = { -2, -1, 0, 0, 1, 2, 3, -9 };
vector<int> arr(a, a + sizeof(a) / sizeof(int));
std::sort(arr.begin(), arr.end(), std::less<int>());
vector<int>::iterator iter = find(arr.begin(), arr.end(), 0);
size_t c = std::count(iter, arr.end(), 0);
vector<int> arrn(arr.begin(), iter);
vector<int> arrz(iter, iter + c);
vector<int> arrp(iter + c, arr.end());
size_t zc = arrz.size();
if (zc > 1)
{
cout << 0;
}
else if (zc == 1)
{
if (arrn.size() % 2 == 0)
{
cout << "times, except 0";
}
else
{
cout << 0;
}
}
else if (zc == 0)
{
if (arrn.size() % 2 == 0)
{
//去掉那个最小的正整数
}
else
{
//去掉那个最大的负整数
}
}
return 0;
}
这个应该比较快了。
Top
4 楼qsc555（石羊山）回复于 2006-12-03 16:38:08 得分 0
oracleot(如风随影) ,
计算 S=a1*a2*....*an; 好像不止是o(n)吧Top
5 楼qsc555（石羊山）回复于 2006-12-03 16:44:32 得分 0
gxqcn(★) HugeCalc ← http://maths.diy.myrice.com/ (☆) ，
(3) 如果 P>0，则剔除其中最小的正整数即可。
如果最大和次最大的负数的积 小于 最小的整数 呢？Top
6 楼qsc555（石羊山）回复于 2006-12-03 16:45:38 得分 0
oracleot(如风随影) ,
计算 S=a1*a2*....*an; 好像不止是o(n)吧
我是指 S1,S2,...,SnTop
7 楼owlling（owlman）回复于 2006-12-03 16:47:08 得分 0
这个问题其实是数组最大子序列问题的变种。可以在O（n）复杂度里解决的
==================================
欢迎访问我的个人主页：http://www.lingjie.net/
==================================Top
8 楼zhangqiurui（）回复于 2006-12-03 20:48:25 得分 0
考虑正负和零的情况后，对所有的数进行排序，然后再处理就很快OK了Top
9 楼qsc555（石羊山）回复于 2006-12-04 14:53:37 得分 0
owlling(owlman) ( 二级(初级)) 信誉：100
你的主页好像访问不了啊，
在这里还多谢各位出主意呢。Top
10 楼owlling（owlman）回复于 2006-12-04 15:01:02 得分 0
我的主页访问不了，。可能是你处在教育网吧？
==================================
欢迎访问我的个人主页：http://www.lingjie.net/
==================================Top
11 楼ppcat_001（）回复于 2006-12-04 15:48:47 得分 0
判断一下是不是有2个0，或者一个0，一个1，那样就不用算了Top
12 楼xjx19（）回复于 2006-12-05 11:59:18 得分 0
先排序,直接求最大的n-1个数的积，可以不？Top
13 楼listart（开始）回复于 2006-12-05 15:10:39 得分 0
遍历数组，记录下最小的正数，最大的负数和零的位置，同时记录下负数的个数
遍历时如果存在零，那么去此零的结果就是解
如果不存在零，那么按负数个数的奇偶分2种情况：
1、偶数个就去掉最小的正数
2、奇数个就去掉最大的负数Top
14 楼YourKing（01240）回复于 2006-12-05 15:32:40 得分 0
将这N个数存储在整型数组A[N]中
1.如果N个数中有>=2个0，无解
2.如果有1个0，计算其他N-1个数的符号位积，如果为正则这N-1个数的乘积为解
如果为负，则有N-1个解
3.如果没有0，计算其他N个数的符号位积，如果为正，找出这N个数中最小正数， 如果为负，找出N个数中最大负数，余下N-1个数的积为解
请指教
Top
15 楼YourKing（01240）回复于 2006-12-05 15:36:49 得分 0
不需要计算数乘积，只要符号位的
一趟循环记录就可以得到所需要的信息Top
16 楼healer_kx（甘草(楼主揭贴吧，我们这些上班灌水的也不容易)）回复于 2006-12-05 15:47:24 得分 0
。。。 。。。
Top
17 楼goodbee（采蜂）回复于 2006-12-05 15:54:23 得分 0
1.如果N个数中有>=2个0，无解
2.如果有1个0，计算其他N-1个数的符号位积，如果为正则这N-1个数的乘积为解
如果为负，则有N-1个解
为什么一个是无解，一个是N-1解？你这N-1个解都为0吧？那如果有两个零，我还不是可以得出那么多乘积为0的？Top
18 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-12-05 15:56:36 得分 0
不知道这里的回帖者是没有看帖的习惯呢？还是出现了阅读理解的障碍？包括对代码的。
老早 healer_kx(甘草) 就给出了非常好（高效）的代码，其算法与本人之前的描述正好完全吻合，
如果各位能仔细阅读理解的话，就无须讨论到现在还不清楚。Top
19 楼YourKing（01240）回复于 2006-12-05 16:17:28 得分 0
为什么一个是无解，一个是N-1解？你这N-1个解都为0吧？那如果有两个零，我还不是可以得出那么多乘积为0的？
===============================
如果有2个0，则用来比较的N个值都是0，所以我说无解
个人觉得有讨论是好事
否则，大家都不要发言了，让版主或星星，嗯，还有那些一答就中的高手来答题好了Top
20 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-12-05 16:26:17 得分 0
在看帖不回帖被鄙视的年代里，流行着回帖不看帖。。。Top
21 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-12-06 10:23:29 得分 0
#include<iostream>
#include <algorithm>
using namespace std;
const bool _comp( const int * const &pL, const int * const &pR )
{
return ( *pL < *pR );
}
int main(int argc, char* argv[])
{
#define LEN 8
int i;
const int ZERO = 0;
const int a[LEN] = { -2, -1, 0, 0, 1, 2, 3, -9 };
const int * ap[LEN];
const int ** pSkip;
for ( i=0; LEN!=i; ++i )
{
ap[i] = &a[i];
}
/* 仅对 a[] 的地址排序，对 a[] 本身不作任何变动 */
sort( ap, ap+LEN, _comp );
pair<const int **, const int **>
pZero = equal_range( ap, ap+LEN, &ZERO, _comp );
switch( pZero.second - pZero.first /* 含“0”的数目 */)
{
case 0:
if (( pZero.first - ap ) & 0x01)
{ /* 有奇数个负数，无零，则剔除一个绝对值最小的负数 */
pSkip = pZero.first - 1 ;
}
else
{ /* 有偶数个负数，无零，则剔除一个绝对值最小的正数 */
if ( ap + LEN != pZero.second )
{
pSkip = pZero.second + 1;
}
else /* 但很不幸，无正数可删，则改删绝对值最大的负数 (※)*/
{
pSkip = ap;
}
}
break;
case 1:
if (( pZero.first - ap ) & 0x01)
{ /* 有奇数个负数，一个零，则可剔除任意一个非零数 */
pSkip = ap;
}
else
{ /* 有偶数个负数，一个零，则剔除掉这个零 */
pSkip = pZero.first;
}
break;
default:/* 有多个零，则可剔除任意某个数 */
pSkip = ap;
}
/* 输出 */
cout << "del: " << **pSkip << endl;
for ( i=0; LEN!=i; ++i )
{
if ( *pSkip != a + i )
{
cout << a[i] << " ";
}
}
cout << endl;
return 0;
}
/* (※)注：与先前的论述相比，多了一种情况：当仅有偶数个负数时，剔除最小的负数 */Top
22 楼xxyyboy（壮志凌云)(★★★★★）回复于 2006-12-06 14:36:53 得分 0
1.去掉 0 ，1
2。绝对值排序
3。奇数个负数，下一步处理，偶数个负数，直接给出结果。
4。取出绝对值最小的最后一个负数与剩下的数中绝对值最大的正数交换，相乘结果1
5。取出绝对值最小的最后一个正数与剩下的数中绝对值最大的负数交换，相乘结果2
6。比较1，2 给出最终结果。
Top
23 楼xxyyboy（壮志凌云)(★★★★★）回复于 2006-12-06 14:38:54 得分 0
题目最好改为
M个整数，求其中任意N-1（M>=N）个数的乘积中的最大的一个。
Top
24 楼itoaer（Maxthon2做的太烂）回复于 2006-12-06 20:18:16 得分 0
这个还是今年google的一个笔试题目Top
25 楼dmt9697（长江9999号）回复于 2006-12-06 22:58:32 得分 0
1.负数个数为奇数，去掉最大的负数(不管有没有0没有关系)
2.负数为偶数:(1).有0去0
(2).没有0去掉最小的正数
变量:fushujiouFlag,zeroFlag,Maxfushu,Minzhengshu
冒泡排序一下，给他们赋值一下就好了Top
26 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-12-07 07:55:32 得分 5
楼上的还是漏了一种情况：全部为负数，且为偶数个（此时应剔除最小的负数）。Top
27 楼houdy（致力于图像/图形领域，成为有思想的程序员）回复于 2006-12-07 15:54:15 得分 0
我来总结一下：
1.定义以下几个变量：
int iMinPositiveNumber -- the min positive number
int iMaxNegativeNumber -- the max positive number
int iNegativeNumberCount -- the count of negative number
bool bZeroExist -- the zero number
2.使用以下的逻辑推理：
if (0 == iNegativeNumberCount%2) {
if (bZeroExist) {
remove zero
}else {
if (0 == iMinPositiveNumber) {
remove the iMaxNegativeNumber;
}else {
remove the iMinPositiveNumber;
}
}
}else {
remove the iMaxNegativeNumber;
}Top
28 楼qsc555（石羊山）回复于 2006-12-23 17:28:46 得分 0
哈哈，谢谢各位参与，本人是很不负责，发了帖子就不管了，今天才肯认真读帖，我觉得
gxqcn(★) HugeCalc ← http://maths.diy.myrice.com/ 最后考虑的比较周全了，但本人不是很熟悉STL的东西，所以开始不愿意认真阅读，现在总结下,如果大家认为没有必要讨论了,我就结帖了:)
/***********************************************************
gxqcn(★) HugeCalc ← http://maths.diy.myrice.com/ ：
该问题等价于：从 N 个整数中剔除一个，使余下的数乘积最大。
令这N个数依次为 a1,a2,...,an，P=a1*a2*...*an，
(1) 如果 P<0，则剔除其中最大的负整数即可；
(2) 如果 P=0，
2.1 若这 N 个数中有且仅有一个为“0”。若其它数之积为正，则剔除“0”；否则剔除任意一个非零数；
2.2 若这 N 个数中至少有两个为“0”，则随便剔除一个均可；
(3) 如果 P>0，则剔除其中最小的正整数即可。
//注明：（3)改为：如果 P>0，如果有正数， 则剔除其中最小的正整数即可；否则，剔除最小的负数；
******************************************************************************/
谢谢xxyyboy(壮志凌云) 提醒，我后来也发现自己误解为：
/******************************************************
题目最好改为
M个整数，求其中任意N-1（M>=N）个数的乘积中的最大的一个。
*******************************************************/
我把题目理解为上述情况了。
healer_kx(甘草 春去春回,花落谁家?心寄笔端,谁解我意?)，我觉得你的代码不错，但正如
/*********************************************************************************
回复人：gxqcn(★) HugeCalc ← http://maths.diy.myrice.com/ (☆) ( 二级(初级)) 信誉：100 2006-12-7 7:55:33
楼上的还是漏了一种情况：全部为负数，且为偶数个（此时应剔除最小的负数）。
**********************************************************************************/
所说的，这段代码
{
//去掉那个最小的正整数
}
还要判断是否有正数的情况。
YourKing(01240) ( 二级(初级)) 信誉：100 ， 我很想知道什么实现，如果阁下能给出
汇编的代码，非常感谢，学习学习:)
我觉得大家都是在考虑算法,但是算法的复杂度和效率能给出吗?本人也想看看别人是什么考虑的,
谢谢各位了.Top
29 楼healer_kx（甘草(楼主揭贴吧，我们这些上班灌水的也不容易)）回复于 2006-12-23 17:32:59 得分 0
看不懂回帖。。。虽然看着很整齐，都不知道谁说了啥。。。
Top
30 楼qsc555（石羊山）回复于 2006-12-25 09:45:31 得分 0
哈哈，本人表达能力不什么好，就此结束吧，似乎没有讨论的必要了；Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
