面试算法 三个数的最大乘积整型数组nums，在数组中找出由三个数字组成的最大乘积，并输出这个乘积。乘积不会越界

1.题目：三个数的最大乘积整型数组nums，在数组中找出由三个数字组成的最大乘积，并输出这个乘积。

约束条件：乘积不会越界

重点考察： 线性扫描

---

2.算法：

1.暴力算法

        先排序完   --->直接返回最大值；

2.线性扫描

        再排序中找到最大值3个 ，最小值2个  ，根据解题思路返回最大值。

---

3.解题思路：

首先三个数的最大值： 有三种情况 

1.数组里面都是   正整数   最大值==  数组里面从小到大的排序之后的       最后三个数

2.  数组里面都是   负整数   最大值==  数组里面从小到大的排序之后的       最后三个数

3.数组里面有正数，有负数， 这时候的最大值有两种情况！ 

        a.  最后三个正数数相乘的积

        b. 最小的两个负数 加上 最大的正数 相乘的积    

        这两个情况取其中的最大值  （这里的时间复杂度 取决于排序算法的速度）

        举例： -3  -2   -1  1      --------> 6

                     -9  -8   -7  2 3  8  9   --------------> (-9) *(-8)  *9

                      -5  -4   -3   -2  -1      ---------------->  (-3)  *   (-2  ) * (-1 )

---

代码：

       

/*************************************************
作者:she001
时间：2022/8/22
内容： 三个数的最大乘积整型数组nums，在数组中找出由三个数字组成的最大乘积，并输出这个乘积。乘积不会越界
重点考察算法:线性扫描
 
 
***************************************************/
#include<bits/stdc++.h>
using namespace std;
 
 
//暴力算法 
// 先排序完--->直接返回最大值；（快排）
 
 
// 其中sort函数用法为：对数组进行排序,其头文件为algorithm.h， 算法时间（n logn） 
//sort()函数可以对给定区间所有元素进行排序。它有三个参数sort(begin, end, cmp)，
//其中begin为指向待sort()的数组的第一个元素的指针，end为指向待sort()的数组的最后一个元素的下一个位置的指针，
//cmp参数为排序准则，cmp参数可以不写，如果不写的话，默认从小到大进行排序。如果我们想从大到小排序可以将cmp参数写为greater<int>()就是对int数组进行排序，
//当然<>中我们也可以写double、long、float等等。如果我们需要按照其他的排序准则，那么就需要我们自己定义一个bool类型的函数来传入。比如我们对一个整型数组进行从大到小排序：
/*
bool cmp(int x,int y){
	return x % 10 > y % 10;
}
*/
 
 
//qsort（）函数用法为，qsort（数组名，元素个数，元素占用的空间（sizeof），比较函数），=====》C语言
 
 //这里我们使用sort 函数
 
 
int cmp_two(int a,int b)
{
	if(a>b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
 
int fangfa_1(int num[],int n)//num 数组    n数组长度 
{
	sort(num,num+n);//排序
	for(int i=0;i<n;i++)
	{
		printf("%d  ",num[i]);
	}
	printf("\n");
	if(n<5)
	{
		printf("长度不符合！\n");
		return 0;
	}	
	else
	{
		int m1,m2;
		m1=num[n-1]*num[n-2]*num[n-3];//三个最大的相乘 
		m2=num[0]*num[1]*num[n-1];//负数的版本 
		return cmp_two(m1,m2);//返回最大的那个数 	
	}	
} 
 
 
 
//2.线性扫描
 
//再排序中找到最大值3个 ，最小值2个? ，根据解题思路返回最大值。
 
int return_big(int num[],int n)//返回最大值 
{
	if(n==0)
	{
		return 0;
	}
	int m=num[0];
	for(int i=0;i<n;i++)
	{
		if(m<num[i])
		{
			m=num[i];	
		}	
	}
	return m; 
	
}
int return_xiao(int num[],int n)//返回最小值 
{
	if(n==0)
	{
		return 0;
	}
	int m=num[0];
	for(int i=0;i<n;i++)
	{
		if(m>num[i])
		{
			m=num[i];	
		}	
	}
	return m; 
}
int fangfa_2(int num[],int n)
{
	int min1=return_big(num,n);
	int min2=return_big(num,n);
	
	int max1=return_xiao(num,n);
	int max2=return_xiao(num,n);
	int max3=return_xiao(num,n);
	for(int i=0;i<n;i++)
	{
		if(num[i]>max1)//第一大的数 
		{
			max3=max2;
			max2=max1;
			max1=num[i];
		}
		else if(num[i]>max2)//第二大的数 
		{
			max3=max2;
			max2=num[i];
		}
		else if(num[i]>max3)//第三大的数 
		{
			max3=num[i];
		}
		
		if(num[i]<min1)
		{
			min2=min1;
			min1=num[i];	
		} 
		else if(num[2]<min2)
		{
			min2=num[i];
		}
	}
	return cmp_two(max1*max2*max3,min1*min2*max1);//返回最大的值	  
}
 
 
int main()
{
	int num[10]={-1,-2,-3,-4,0,4,8,9,5,3};
	int a=fangfa_1(num,10);
	printf("方法一  a=%d\n",a);
	printf("\n");
	a=fangfa_2(num,10);
	printf("方法二  a=%d\n",a);
	
	int num1[10]={-10,-20,-3,-4,0,4,8,9,5,3};
	int b=fangfa_1(num1,10);
	printf("方法一  a=%d\n",b);
	printf("\n");
	a=fangfa_2(num,10);
	printf("方法二  a=%d\n",b);
	return 0;
}