Codility 'MaxProductOfThree' Solution | MartinKysel.com
Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).
Link: MaxProductOfThree
http://codility-lessons.blogspot.com/2014/07/the-trick-is-to-produce-max-product-we.html
The trick is to produce a max product, we have to consider any two of the three picked up values can be negative. In this case, the product of these two negative values can be positive.
So what we need to do is to compute the product of two smallest values and one biggest values and the product of three biggest values.
The bigger one of these two will be the maximum product.
there is an O(N) solution. We sort the input in the original solution, because we want the two minimum and three maximum elements.
However, with bookkeeping, sorting is not necessary.
Read full article from Codility 'MaxProductOfThree' Solution | MartinKysel.com
Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).
Link: MaxProductOfThree
After sorting the largest product can be found as a combination of the last three elements. Additionally, two negative numbers add to a positive, so by multiplying the two largest negatives with the largest positive, we get another candidate. If all numbers are negative, the three largest (closest to 0) still get the largest element!
def solution(A): if len(A) < 3: raise Exception("Invalid input") A.sort() return max(A[0] * A[1] * A[-1], A[-1] * A[-2] * A[-3])http://codility-lessons.blogspot.com/2014/07/the-trick-is-to-produce-max-product-we.html
The trick is to produce a max product, we have to consider any two of the three picked up values can be negative. In this case, the product of these two negative values can be positive.
So what we need to do is to compute the product of two smallest values and one biggest values and the product of three biggest values.
The bigger one of these two will be the maximum product.
there is an O(N) solution. We sort the input in the original solution, because we want the two minimum and three maximum elements.
However, with bookkeeping, sorting is not necessary.
public int solution(int[] A) {
int[] maxes = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
// Invariant: maxes[0] <= maxes[1] <= maxes[2]
int[] mins = {Integer.MAX_VALUE, Integer.MAX_VALUE};
// Invariant: mins[0] <= mins[1]
// O(n)
for( int a : A )
{
updateMaxes( a, maxes );
updateMins( a, mins );
}
System.out.println(Arrays.toString(maxes));
System.out.println(Arrays.toString(mins));
int obvious = maxes[0] * maxes[1] * maxes[2];
int twoBigNegs = mins[0] * mins[1] * maxes[2];
return Math.max( obvious, twoBigNegs );
}
private static void updateMaxes( int a, int[] maxes )
{
if( a >= maxes[2] ) {
// Found new max, shift down
maxes[0] = maxes[1];
maxes[1] = maxes[2];
maxes[2] = a;
} else if( a >= maxes[1] ) {
maxes[0] = maxes[1];
maxes[1] = a;
} else if( a > maxes[0] ) {
maxes[0] = a;
}
}
private static void updateMins( int a, int[] mins )
{
if( a <= mins[0] ) {
// Found new min, shift down
mins[1] = mins[0];
mins[0] = a;
} else if( a < mins[1] ) {
mins[1] = a;
}
}
Read full article from Codility 'MaxProductOfThree' Solution | MartinKysel.com
