题目

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

1
2
Input: [1,2,3]
Output: 6

Example 2:

1
2
Input: [1,2,3,4]
Output: 24

Note:

1
2
The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].  
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

分析

这是一道读题的题目,这是第二次出现快速排序,分析在注释中。

代码+注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

/*
* 设计知识点:
快速排序(减少时间复杂度,减少时间)

* 错误用例
* Input:
[-4,-3,-2,-1,60]
Output:
120
Expected:
720
* 错误:
* 1. 测试用例中出现了负数导致产品的值出现了比较错误,使实际的输出值不是最大
* 解决方案
* 1.采用将全部的数值转换成整数的方案
* 缺点
* 1.会使得最后的结果出错(错误无法避免,切换解决方案)
*方案2:
* 分别判断,分别返回
*
* 错误用例
* [722,634,-504,-379,163,-613,-842,-578,750,951,-158,30,-238,-392,-487,-797,-157,-374,999,-5,-521,-879,-858,382,626,803,-347,903,-205,57,-342,186,-736,17,83,726,-960,343,-984,937,-758,-122,577,-595,-544,-559,903,-183,192,825,368,-674,57,-959,884,29,-681,-339,582,969,-95,-455,-275,205,-548,79,258,35,233,203,20,-936,878,-868,-458,-882,867,-664,-892,-687,322,844,-745,447,-909,-586,69,-88,88,445,-553,-666,130,-640,-918,-7,-420,-368,250,-786]
*错误2 :
* 低估了数组的大小
*解决方案:
* 扩充int到long
* 看了下大佬的还真是棒 而且简单的很 site:http://www.cnblogs.com/grandyang/p/7084957.html
* */
#include <stdio.h>
void quiksort(int a[],int low,int high)
{
int i = low;
int j = high;
int temp = a[i];

if( low > high)
{
return ;
}
while(i < j)
{
while((a[j] >= temp) && (i < j))
{
j--;
}
a[i] = a[j];
while((a[i] <= temp) && (i < j))
{
i++;
}
a[j]= a[i];
}
a[i] = temp;
quiksort(a,low,i-1);
quiksort(a,j+1,high);
}
int maximumProduct(int* nums, int numsSize) {
quiksort(nums,0,numsSize-1);
// 当nums[numsSize-1]<=0 即全部均小于零 则 nums[0]*nums[1]*nums[numsSize-1]最大
/*if(nums[numsSize-1]<=0)
{
return nums[0]*nums[1]*nums[numsSize-1];
} else if(nums[numsSize-2]<0)
{
// 此时 nums[numsSize-1]>0 &&nums[numsSize-2]<0] 此时返回nums[0]*nums[1]*nums[numsSize-1]
return nums[0]*nums[1]*nums[numsSize-1];
} else if(nums[numsSize-2]==0) {
// 此时直接返回0
return 0;
}else if(nums[numsSize-3]<=0)
{
return nums[numsSize-1]*nums[numsSize-2]*nums[numsSize-3];
}
return nums[numsSize-3]*nums[numsSize-2]*nums[numsSize-1];*/
int max=0,max1;
max=nums[numsSize-1]*nums[0]*nums[1];
max1=nums[numsSize-1]*nums[numsSize-2]*nums[numsSize-3];
if(max>max1)
{
return max;
} else
{
return max1;
}

}
int main()
{
int nums[]={722,634,-504,-379,163,-613,-842,-578,750,951,-158,30,-238,-392,-487,-797,-157,-374,999,-5,-521,-879,-858,382,626,803,-347,903,-205,57,-342,186,-736,17,83,726,-960,343,-984,937,-758,-122,577,-595,-544,-559,903,-183,192,825,368,-674,57,-959,884,29,-681,-339,582,969,-95,-455,-275,205,-548,79,258,35,233,203,20,-936,878,-868,-458,-882,867,-664,-892,-687,322,844,-745,447,-909,-586,69,-88,88,445,-553,-666,130,-640,-918,-7,-420,-368,250,-786};
int numsSize= sizeof(nums)/ sizeof(int);
printf("%d",maximumProduct(nums,numsSize));
return 0;
}