[牛客网]最大乘积

给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)

代码

   class Solution 
{
public:
void FindMax()
{
	int n;
	long result;
	cin >> n;
	int *a=new int[n];//用指针a指向NEW动态分配的长度N的内存空间
	long long  max = 1; long long  max_sec = 1; long long  max_third = 1;
	long long  min = 1; long long  min_sec = 1;
       if (n<3)
           return ;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		if (a[i] > max)
		{
			max_third = max_sec;
			max_sec = max;
			max = a[i];
		}
		else if (a[i] > max_sec)
		{
			max_third = max_sec;
			max_sec = a[i];
		}
		else if (a[i] > max_third)
		{
			max_third = a[i];
		}
		else if (a[i] < min)
		{
			min_sec = min;
			min = a[i];
		}
		else if (a[i] < min_sec)
			min_sec = a[i];
		long max1 = max * max_sec*max_third;
        long max2 = max * min*min_sec;
		if (max1 >= max2)
			result = max1;
		else
			result = max2;
           
	}
       cout<<result<<endl;
}

   };
   int main()
   {
       Solution s;
       s.FindMax();
   }

算法：

因为要求时间复杂度是N，所以只能有循环。
当数组大小小于3的时候，直接返回。

最大乘积只有两种可能：

1:三个最大正数相乘

2：一个最大正数和两个最小负数

所以在循环的时候只要找到这五个数。初始化的时候这五个数可以都初始化为1，在循环中，不断改变它们的值。最后将两种情况比较，输出最大值。

易错点：

关于数据的溢出，第一次写的时候把所有的数据类型都定义成int型，但是通过率只有22%，这里没有规定数据大小，所以要注意溢出的问题

疑问

n=3的情况怎么判断？如果是一个负数两个正数，输出的是什么？代码直接判断了两个正数相乘输出没有报错通过了？

int ,long , long long类型的范围

unsigned int 0～4294967295
int -2147483648～2147483647
unsigned long 0～4294967295
long -2147483648～2147483647
long long的最大值：9223372036854775807
long long的最值：-9223372036854775808
unsigned long long的最大值：18446744073709551615

int64的最大值：9223372036854775807 int64的最小值：-9223372036854775808
unsigned __int64的最大值：18446744073709551615

32位下，shrot int long分别是2字节，4字节，4字节，longlong是8字节；

64位下，long8字节 int是4字节，longlong 8字节。

int是4字节的，一个字节代表8位二进制，所以int的数据类型是32位。所以可以表示2的32次幂的位数，但是数有正有负，所以是-2的32/2=2的31次到2的31次-1