题解 | #三个数的最大乘积#

C++：顺便回顾一下快速排序。最大乘积：负负得正再乘以最大，或者三个最大的数相乘。最大的数可能是这两者的一个。那么就好办了，排序一上就完成了。

class Solution {
public:
    /**
     * 最大乘积
     * @param A int整型一维数组 
     * @param ALen int A数组长度
     * @return long长整型
     */
    long long solve(int* A, int ALen) {
        // write code here
        quickSort(A, ALen, 0, ALen-1);
        return max((long long)A[0]*A[1]*A[ALen-1],(long long)A[ALen-1]*A[ALen-2]*A[ALen-3]);
    }
    void quickSort(int* A, int Alen, int low, int high){
        if(low < high){
            int mid = partition(A, Alen, low, high);
            quickSort(A,Alen, low, mid - 1);
            quickSort(A, Alen, mid + 1, high);
        }
    }
    int partition(int* A, int Alen, int low, int high){
        int pivot = A[low];
        while(low < high){
            while(low < high && A[high] >= pivot)high--;
            A[low] = A[high];
            while(low < high && A[low] <= pivot)low++;
            A[high] = A[low];
            A[low] = pivot;
        }
        return low;
    }
};