问不排序求解三个数组元素的最大乘积

EN

/*    The method get the max product of 3 consists in basically find the biggest 3 numbers from the array and the smallest 2 numbers from the array in just 1 iteration over the array. Here is the java code:*/

    int solution(int[] a) {
/* the minimums initialized with max int to avoid cases with extreme max in array and false minims 0 minimums returned */

        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
/* the same logic for maximum initializations but of course inverted to avoid extreme minimum values in array and false 0 maximums */

        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;

//the iteration over the array

        for (int i = 0; i < a.length; i++) {

//test if max1 is smaller than current array value

            if (a[i] > max1) {
            //if a[i] is greater than the biggest max then a chain reaction is started,
            // max3 will be max2, max2 will be actual max1 and max1 will be a[i]    
                max3=max2;
                max2=max1;
                max1=a[i];
/* in case if current a[i] isn't bigger than max1 we test it to see maybe is bigger than second
 max. Then the same logic from above is applied for the max2 amd max3 */

            }else if(a[i]>max2){
                max3 = max2;
                max2 = a[i];
/* finally if current array value isn't bigger than max1 and max2 maybe is greater than max3 */

            }else if(a[i]>max3){
                max3 = a[i];
            }

/* The logic from above with maximums is is applied here with minimums but of course inverted to
discover the 2 minimums from current array. */

            if (a[i] < min1) {
                min2 =min1;
                min1=a[i];
            } else if (a[i] < min2) {
                min2 = a[i];
            }
        }
/* after we discovered the 3 greatest maximums and the 2 smallest minimums from the array
we do the 2 products of 3 from the greatest maximum and the 2 minimums . This is necessary
because mathematically the product of 2 negative values is a positive value, and because of
this the product of min1 * min2 * max1 can be greater than max1 * max2 * max3
 and the product built from the the 3 maximums. */

        int prod1 = min1 * min2 * max1;
        int prod2 = max1 * max2 * max3;

//here we just return the biggest product

        return prod1 > prod2 ? prod1 : prod2;

    } 

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.Arrays;

class Solution {

    public int solution(int[] A) {

        int N = A.length;
        Arrays.sort(A);

        /**
         * When we sort an array there are two possible options for the largest product
         * 1) The largest (the last) three elements
         * 2) Combination of two smallest and the largest elements
         * Logic of (1): Obvious
         * Logic of (2): A pair of negatives multiplied returns a positive, which in combination with 
         * the largest positive element of the array can give the max outcome.
         * Therefore we return the max of options (1) and (2)
         */
        return Math.max(A[0] * A[1] * A[N - 1], A[N - 1] * A[N - 2] * A[N - 3]);
    }
}

#include<limits>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int solution(vector<int> &A) {
    //Keep the absolute value for max 2 -ve num . As their mul will be +ve
    int abs1 = numeric_limits<int>::min();
    int abs2 = numeric_limits<int>::min();

    //Keep the max three num irrespective of sign
    int max1 = numeric_limits<int>::min();
    int max2 = numeric_limits<int>::min();
    int max3 = numeric_limits<int>::min();

    unsigned int size = A.size()-1;

    for (unsigned int i = 0; i <= size ; ++i) {
        if(A[i] > 0 ){

        } else if(abs(A[i]) >= abs1 ) {
            abs2 = abs1;
            abs1 = abs(A[i]);
        }else if(abs(A[i]) >= abs2 ) {
            abs2 = abs(A[i]);
        }

        if(A[i] >= max1 ){
            //Push max1s prev value to max2 and max2's prev val to max3
            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];
        }
    }
    // Either max 3 multiplication , or Max 2 negative num whose mul is +ve and the regular max
    return max(max1 * max2 * max3, abs1 * abs2 * max1);
}


int main(){
    vector<int> test = {-3, 1, 2, -2, 5, 6};
    cout << solution(test);
    return 0;
}