628.三个数的最大乘积

发表于 | 分类于
字数统计: 318 | 阅读时长 ≈ 1

一、题目描述

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1:

1
2
输入: [1,2,3]
输出: 6

示例 2:

1
2
输入: [1,2,3,4]
输出: 24

注意:

  1. 给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
  2. 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。

二、题解

1.算法描述

  • 排序、选数

2.个人分析

  1. 对数组进行升序排序

  2. 最大乘积：

    1. 全是正数：选三个最大的
    2. 全是负数：还选三个最大的
    3. 有正有负：
      • [-4, 0, 2, 3] : 选三个最大的
      • [-4, -3, 1, 2] : 选两个负的一个正的

  3. 所以最大乘积只有两种情况：

    • 第一个负数的绝对值比较小倒着选三个数
    • 正着选两个数，倒着选一个数

  4. 选两个数中的较大数

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
int compare1(const void *a, const void *b)
{ //升序
    return (*(int *)a - *(int *)b);
}
int maximumProduct(int *nums, int numsSize)
{
    if (numsSize == 3)
        return nums[0] * nums[1] * nums[2];
    qsort(nums, numsSize, sizeof(int), compare1);
    int max1 = nums[numsSize - 1] * nums[numsSize - 2] * nums[numsSize - 3];
    int max2 = nums[0] * nums[1] * nums[numsSize - 1];
    return max1 > max2 ? max1 : max2;
}