628. Maximum Product of Three Nu

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:
The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

分析

本题需要求数组中3个数相乘的最大值，数有正有负，说明需要考虑有负数的情况下两个负数相乘得正的情况。
那么乘积最大时，有哪些情况呢？

1. 都是正数（包括0），最大的3个数相乘积最大
2. 都是负数，最大的3个数相乘积最大
3. 有正数也有负数，负数至少2个，那么最大正数与最小两个负数的乘积最大
4. 有正数也有负数，负数1个，那么最大的3个正数相乘积最大

因此，我们只需要知道数组中最大的3个数和最小的2个数即可，然后取最大3个数的乘积与最大数和最小两个数乘积的较大者即可。遍历一次数组即可求得。

code

class Solution {
    public int maximumProduct(int[] nums) {
        int max1, max2, max3, min1, min2;
        max1 = max2 = max3 = Integer.MIN_VALUE;
        min1 = min2 = Integer.MAX_VALUE;
        for (int n : nums) {
          if (n > max1) {
            max3 = max2;
            max2 = max1;
            max1 = n;
          }
          else if (n > max2) {
            max3 = max2;
            max2 = n;            
          }
          else if (n > max3) {
            max3 = n;
          }
          if (n < min1) {
            min2 = min1;
            min1 = n;
          }
          else if (n < min2) {
            min2 = n;
          }
        }
        return Math.max(max1*max2*max3, max1*min1*min2);
    }
}