LeetCode Maximum Product of Three Numbers

LeetCode Maximum Product of Three Numbers

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.

给定一个整数数组,选出三个数,使得乘积最大。

整数数组中可能有负数,所以我们先对数组从小到大排序。如果最小值都大于0,说明没有负数,则三数乘积最大就是最大的前3个数的乘积。

如果有负数,且至少有两个负数,则还需要判断一下最小的两个负数乘以最大的正数的乘积,这个数和前一种情况的大小关系。

代码如下:

class Solution {
public:
	int maximumProduct(vector<int>& nums) {
		int n = nums.size();
		sort(nums.begin(), nums.end());
		int ans1 = nums[n - 1] * nums[n - 2] * nums[n - 3], ans2 = 0;
		if (nums[0] > 0)return ans1;
		if (nums[0] < 0 && nums[1] < 0)ans2 = nums[0] * nums[1] * nums[n - 1];
		return max(ans1, ans2);
	}
};

本代码提交AC,用时73MS。

Leave a Reply

Your email address will not be published. Required fields are marked *