算法笔记(模拟最大三数乘积问题)

问题:给定一个无序整型数组，可能包含正数，负数和0，在数组中找出由三个数组成的最大乘积，并输出。

分类讨论有九种情况:

1.两个负数，一个正数

2.三个全是正数

3.三个全是负数

4.两个正数，一个负数

5. 两个负数，一个零

6.两个正数，一个零

7.三个全是零

8.一个正数，两个零

9.一个负数，两个零

本来想用两种排序(绝对值排序，非绝对值排序)来枚举求解，但是有点繁琐。发现规律后，只要非绝对值排序，然后求两个结果取最大值即可。

四种情况中，2，3，4，5，6，7，8，9的计算方法其实是一样，都是递增排序后的最后3个数的乘积；而1的计算方法则是递增排序后的第一个数，第二个数以及最后一个数的乘积。

给出几个样例可以自行验证:

-5 -3 -1 0 3 5

0 1 2 3 4 5

-6 -4 -2 -1?

-6 -4 -2 -1 0

-3? 0 5?10

-5 -3 -1 3 5

#include<stdio.h>

void InsSort(int arr[],int len){
	for(int i=1; i<len; ++i){
		int insert=arr[i];
		int index=i-1;
		while(index>=0 && insert<arr[index]){
			arr[index+1]=arr[index];
			--index;
		}
		arr[index+1]=insert;
	}
}

int MaxValue(int a,int b){
	return a>b?a:b;
}

int main() {
	int n;
	scanf("%d",&n);
	int a[n];
	for(int i=0; i<n; i++)
		scanf("%d",&a[i]);
	InsSort(a,n);
	int res1=a[0]*a[1]*a[n-1];//两负一正
	int res2=a[n-1]*a[n-2]*a[n-3];
    //三正或两正一负或三负或两负一零或两正一零或全零或一正两零或一负两零
	printf("%d",MaxValue(res1,res2));
}