Epoch

題目

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, 10^4] 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.

想法

    記錄最大的三個數字，最後相乘；但可能會有例外，兩個很小的負數相乘，可以得到一個很大的正數，因此也要記錄兩個最小的負數。

code

    int maximumProduct(int* nums, int numsSize) {
    int m1 = 0, m2, m3;
    int max1 = -9999, max2, max3;
    int num1 = 0, num2 = 0;
    int n = 0;
    for (int i=0; i<numsSize; i++) {
        if (nums[i]<0) {
            if (m1 > nums[i]) {
                m2 = m1;
                m1 = nums[i];
            } else if (m2 > nums[i]) {
                m2 = nums[i];
            }
        }
        if (max1 < nums[i]) {
                max3 = max2;
                max2 = max1;
                max1 = nums[i];
        } else if (max2 < nums[i]) {
                max3 = max2;
                max2 = nums[i];
        } else if (max3 < nums[i]) {
                max3 = nums[i];
        }
    }
    num1 = m1 * m2 * max1;
    num2 = max1 * max2 * max3;
    if (num1 > num2)
        return num1;
    else
        return num2;
    
}