[LeetCode] 628. Maximum Product of Three Numbers

轉自LeetCode

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

Example 1:

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

Example 2:

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

Note:

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

<Solution>

想法如下

• 先對array做排序( O(nlogn))

• 要特別注意的是有負數的情況，因為兩個負數相乘會變正數，所以最小的兩個負數和最大的正數三個相乘，也有可能比最大的三個正數相乘還大，這點要特別注意

code 如下

Java

	class Solution {
	public int maximumProduct(int[] nums) {
	Arrays.sort(nums);
	return Math.max(nums[0]*nums[1]*nums[nums.length-1], nums[nums.length-3]*nums[nums.length-2]*nums[nums.length-1]);
	}
	}

view raw maximumProduct.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun maximumProduct(nums: IntArray): Int {
	nums.sort()
	return Math.max(nums[0]*nums[1]*nums[nums.lastIndex], nums[nums.lastIndex]*nums[nums.lastIndex-1]*nums[nums.lastIndex-2])
	}
	}

view raw maximum_product_of_three_numbers.kt hosted with ❤ by GitHub