Maximum Product
June 11, 2019
I think today’s exercise comes from one of those hacker testing sites, but I’m not sure:
Given three arrays of integers, both positive and negative, find the maximum product that can be formed by taking one element from each array. For instance, if A = [10,-10,15,-2], B = [10,-12,13,-2], and C = [-11,-10,9,-12], the maximum product is 2160 using 15, -12 and -12.
Your task is to write a program that finds the maximum product of three integers, taking one each from three arrays. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Cool problem. Here is my take on it using Julia 1.0.2:
function fmp(A::Array{Int64, 1}, B::Array{Int64, 1}, C::Array{Int64, 1})
Aa = abs.(A)
na = length(A)
ind_a = sortperm(Aa, rev = true)
Ba = abs.(B)
nb = length(B)
ind_b = sortperm(Ba, rev = true)
Ca = abs.(C)
nc = length(C)
ind_c = sortperm(Ca, rev = true)
mp = typemin(Int64)
Z = Array{Int64}(undef, 3)
counter = 0
iwp = round(Int64, sqrt(nanbnc)) # iterations without progress
end
Note that to avoid unnecessary iterations, I limited the total number of iteration by including the iwp threshold (iterations without progress). This is heuristically calculated using the sizes of the original arrays as an input. Tried it with larger arrays and it works, though I cannot vouch for its effectiveness for all sizes. Cheers!
Here is a simple R7RS Scheme solution to a slightly more general
problem; it works for one or more “arrays” (lists) of numbers as
input.
(import (scheme base) (scheme write)) (define (max-product nums . lst) (let loop ((hi (apply max nums)) (lo (apply min nums)) (lst lst)) (if (null? lst) hi (let* ((chi (apply max (car lst))) (clo (apply min (car lst))) (prods (list (* hi chi) (* hi clo) (* lo chi) (* lo clo)))) (loop (apply max prods) (apply min prods) (cdr lst)))))) (display (map (lambda (lsts) (apply max-product lsts)) '(((10 -10 15 -2) (10 -12 13 -2) (-11 -10 9 -12)) ((10 -10 15 -2) (1 -1 -100 3) (-33 39 4 3 1 4 1 5 9) (10 -12 13 -2) (-11 -10 9 -12))))) (newline)Slightly more general in Perl – but uses a similar technique – written to allow any number of arrays
@I=( [10,-10,15,-2], [10,-12,13,-2], [-11,-10,9,-12] ); ## Initialize + get min/max values for each array $q,@x=[1],map{[(sort{$a<=>$b}@{$_})[0,-1]]}@I; ## This loops through min/max values generating a new $q with the multiplication performed; $t=$_,$q=[(map{$_*$t->[0]}@{$q}),(map{$_*$t->[1]}@{$q})]for@x; ## Choose the largest value say'',(sort{$a<=>$b}@{$q})[-1];In Python. Only eight product are possible. Simple calculate the maximum of these eight. Reducing the number of products to four hardly reduces calculation time and only makes things more complicated.
from itertools import product from functools import reduce from operator import mul def bf(A, B, C): minmax = [(min(arr), max(arr)) for arr in (A, B, C)] return max((reduce(mul, p) for p in product(*minmax)))@Zack: I don’t understand how the ‘iwp’ cutoff is correct. If there is a very large item at the end of array C, won’t it be missed? Also, your method seems to be Theta(n^3) instead of the other Theta(n) solutions.
@Paul: that’s a good question. That’s why I sort the arrays first, in terms of absolute values. Chances are that the first iterations of the loops are going to yield the optimum result, so we never have to go through all possible combinations (something wasteful for large arrays). The latter are more than 8 for the original arrays, btw; namely Total_Combinations = 4 x 4 x 4 = 64. Cheers
Rust version:
type V4 = [i64; 4]; fn maxit(a: V4, b: V4, c: V4) -> i64 { let mut max = a[0]*b[0]*c[0]; for x in &a { for y in &b { for z in &c { if max < x*y*z { max = x*y*z; } } } } max } fn main() { dbg!(maxit([10,-10,15,-2], [10,-12,13,-2], [-11,-10,9,-12])); }Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=377bd1520d7bd51bb59bd268c654eab4
Here’s a solution in C.
#include <limits.h> #include <stdio.h> #include <stdlib.h> void max_min(int* array, int n, int* max, int* min) { *max = INT_MIN; *min = INT_MAX; for (int i = 0; i < n; ++i) { if (array[i] > *max) *max = array[i]; if (array[i] < *min) *min = array[i]; } } int maximum_product( int* a1, int n1, int* a2, int n2, int* a3, int n3) { int max1; int min1; int max2; int min2; int max3; int min3; max_min(a1, n1, &max1, &min1); max_min(a2, n2, &max2, &min2); max_min(a3, n3, &max3, &min3); int r1 = max1 * max2 * max3; int r2 = max1 * max2 * min3; int r3 = max1 * min2 * max3; int r4 = max1 * min2 * min3; int r5 = min1 * max2 * max3; int r6 = min1 * max2 * min3; int r7 = min1 * min2 * max3; int r8 = min1 * min2 * min3; int result = r1; result = result > r2 ? result : r2; result = result > r3 ? result : r3; result = result > r4 ? result : r4; result = result > r5 ? result : r5; result = result > r6 ? result : r6; result = result > r7 ? result : r7; result = result > r8 ? result : r8; return result; } int main(int argc, char* argv[]) { int code = EXIT_FAILURE; int* array = malloc(sizeof(int) * (argc - 1)); int array_idx = 0; int idx = 0; int n[3] = {0}; for (int i = 1; i < argc; ++i) { if (array_idx > 2) goto end; if (argv[i][0] == '.') { ++array_idx; continue; } array[idx++] = atoi(argv[i]); ++(n[array_idx]); } if (array_idx != 2) goto end; int result = maximum_product( array, n[0], array + n[0], n[1], array + n[0] + n[1], n[2]); printf("%d\n", result); code = EXIT_SUCCESS; end: free(array); return code; }Example Usage: