给定一个长度为N的整数数组，计算任意(N-1)个数的组合中乘积最大的一组，算法的时间复杂度为O(N)

分析与解法

遍历一遍数组，求出数组中正数(+),负数(-)和0的个数,从而判断N个数乘积的正负性,依此判断是去掉0,还是最小的负数,还是最大的负数,还是最小的正数来得到目标的N-1个数,使乘积最大。

例如:集合全为负数时,去掉最小负数;全为正数时去掉最小正数;等等还有很多种情况.

主要要考虑集合中0的个数与集合中负数的个数以及全为负数的情况。

C# Codes

namespace ConsoleApp2010
{
class Program
{
static void Main(string[] args)
{
System.Console.WriteLine(FindItem(new int[] { -1, -2, -3, -4}));
System.Console.ReadKey();
}


static int FindItem(int[] array)
{
int length = array.Length;
int negativeNum = 0;
int maxNegative = 0;
int minNegative = 0;
int minPositive = 0;
int zeroNum = 0;


for (int i = 0; i < length; i++)
{
if (array[i] < 0)
{
negativeNum++;


if (maxNegative == 0 || maxNegative < array[i])
{
maxNegative = array[i];
}


if (minNegative == 0 || minNegative > array[i])
{
minNegative = array[i];
}
}
else if (array[i] == 0)
{
zeroNum++;
}
else
{
if (minPositive == 0 || minPositive > array[i])
{
minPositive = array[i];
}
}
}


int result;


if (zeroNum > 1)
{
result = 0;
}
else if (zeroNum == 1)
{
if (negativeNum % 2 == 0)
{
result = 0;
}
else
{
result = maxNegative;
}
}
else
{
if (negativeNum % 2 == 0)
{
if (minPositive != 0)
{
result = minPositive;
}
else
{
result = minNegative;
}
}
else
{
result = maxNegative;
}
}


return result;
}
}
}