JAVA算法:求数组中三个数相乘的最大乘积
给定一个整型数组,在数组中找出由三个数组成的最大乘积,并输出这个乘积。
注意:
- 给定的整型数组长度范围是[3,10^4],数组中所有的元素范围是[-1000, 1000]。
- 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
问题分析
给定的数组中,有整数,也有负数,甚至还有零。
则首先对给定的数组进行排序。
然后分下面几种情况讨论:
- 如果排序后的数组的最大元素为负数,则说明数组元素均为负数。例如,给定数组排序之后为 [-100,-98,-7,-2-,1],则最大乘积为负值,其数值为最后三个数组元素的乘积。
- 如果排序后的数组的最大元素为正数,则又需要分情况讨论:
- 数组中所有元素均为正数,则最大值为最后三个数组元素的乘积;
- 数组中元素有正数,也有负数;这时候就需要进行比较了;用最后三个数组元素的乘积与最大元素和数组中前两个元素乘积进行比较,取其中较大的值。
算法设计
public int maximumProduct(int[] nums) {//对数组元素进行排序,小的在前,大的在后Arrays.sort(nums);//取数组元素的长度int len = nums.length;//如果最大元素为负值;则最后3个数组元素的乘积为最大值