628. 三个数的最大乘积

Introduction

Question：628. 三个数的最大乘积

Analysis

通过归纳总结可以得出一个结论，在排序后，最大乘积只能从这两个值中取：

• nums[size - 1] * nums[size - 2] * nums[size - 3]
• nums[0] * nums[1] * nums[size-1]

Implement

int maximumProduct(vector<int>& nums) {
    // sort(nums)
    // 1. nums[i] >= 0，-> nums[-1] * nums[-2] * nums[-3]
    // 2. nums[i] <= 0, -> nums[-1] * nums[-2] * nums[-3]
    // 3. nums[0:i] <= 0, nums[i:] > 0, -> max{ nums[0]*nums[1]*nums[-1], nums[-1] * nums[-2] * nums[-3],  }
    // 如果
    sort(nums.begin(), nums.end());
    int size = nums.size();

    return max(nums[size - 1] * nums[size - 2] * nums[size - 3], nums[0]*nums[1]*nums[size-1]);
}