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

class Solution {
public:
    /**
     * 最大乘积
     * @param A int整型一维数组 
     * @param ALen int A数组长度
     * @return long长整型
     */
    //考虑三种情况
    // 1. 全为正数
    // 2. 全为负数
    // 3. 同时有正数和负数
    
//     long long solve(int* A, int ALen) {
//         // write code here
//         //最小、第二小的数
//         int min1 = INT_MAX , min2 = INT_MAX;
//         //最大、第二大、第三大
//         int max1 = INT_MIN , max2 = INT_MIN , max3 = INT_MIN;
//         for(int i = 0;i < ALen;i++){
//            if(A[i] < min1){
//                min2 = min1;
//                min1 = A[i];
//            }else if(A[i] < min2){
//                min2 = A[i];
//            }
//            if(A[i] > max1){
//                max3 = max2;
//                max2 = max1;
//                max1 = A[i];
//            }else if(A[i] > max2){
//                max3 = max2;
//                max2 = A[i];
//            }else if(A[i] > max3){
//                max3 = A[i];
//            }
//         }
//         return max((long)min1 * min2 * max1,(long)max1 * max2 * max3);
//     }
    
    long long solve(int* A, int ALen) {
        // write code here
        //找出最大的三位数，放在数组的最后,时间复杂度 O(3n)
        for(int i =0 ;i < 3;i++){
            for(int j = 0; j < ALen - 1 - i;j++){ 
                if(A[j] > A[j + 1]){
                    int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                }
            }
        }
        //找出最小的两位数，放在数组的最前面，时间复杂度 O(2n)
        for(int i = 0 ;i < 2;i++){
            for(int j = ALen - 1; j > i;j--){
                if(A[j] < A[j - 1]){
                    int temp = A[j];
                    A[j] = A[j - 1];
                    A[j - 1] = temp;
                }
            }
        }
        return max((long)A[0] * A[1] * A[ALen - 1],(long)A[ALen - 1] * A[ALen - 2] * A[ALen - 3]);
    }
};