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; } };