Find a pair with maximum product in array of Integers 找出数组中最大乘积的一对

给一个数组, 找出里面的两个数, 使得这两个数的乘积最大.这是geeksforgeeks上的题, 我看原题下面的代码有点复杂, 就重新想了想.

先看两个例子:

Input: arr[] = {1, 4, 3, 6, 7, 0}  
Output: {6,7}  

Input: arr[] = {-1, -3, -4, 2, 0, -5} 
Output: {-4,-5}

但是上面的例子不能完全说明问题, 比如说{0,1,-5}, 这时候, pair应该是0, 1 OR 0, -5.

思路很简单, 通过观察上面的例子, 不难发现, 这个pair和四个数字有关: 数组中, 正数的最大值pmax和第二大值psec, 负数的最大值nmax和第二大值nsec. 而最大值应为Math.max(pmax*psec, nmax*nsec).

代码如下:

 public int[] find(int[] nums) {
        if (nums == null || nums.length == 0)
            return new int[]{};
        int[] res= new int[2];
        int pmax= 0,psec = 0; //pmax 是positive最大,psec是第二大
        int nmax= 0,nsec = 0; //nmax 是negative最小,nsec是第二小
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0){
                if (nums[i] > pmax) {
                    psec = pmax; // 更新max时, 要把max给sec.
                    pmax = nums[i];
                }
                else if (nums[i] > psec)
                    psec = nums[i];
            }
            else if (nums[i] < 0) {
                if (nums[i] < nmax) {
                    nsec = nmax;// 更新max时, 要把max给sec.
                    nmax = nums[i];
                }
                else if (nums[i] < nsec)
                    nsec = nums[i];
            }
        }
        if (pmax*psec > nmax*nsec)
            return new int[]{pmax,psec};
        else
            return new int[]{nmax,nsec};
    }

需要注意的是else if在判断时候使用, 还有初始化时,应该把值初始为0.