Maximum Product

June 11, 2019

There are four ways the maximum product can be formed:

1) take the maximum from each of the three arrays
2) take the maximum from the first array and the minimum from the second and third arrays
3) take the maximum from the second array and the minimum from the first and third arrays
4) take the maximum from the third array and the minimum from the first and second arrays:

(define (max-prod xs ys zs)
  (let ((min-x (apply min xs)) (max-x (apply max xs))
        (min-y (apply min ys)) (max-y (apply max ys))
        (min-z (apply min zs)) (max-z (apply max zs)))
    (max (* max-x max-y max-z)
         (* max-x min-y min-z)
         (* min-x max-y min-z)
         (* min-x min-y max-z))))

And here is the program applied to the sample problem.

> (max-prod '(10 -10 15 -12) '(10 -12 13 -12) '(-11 -10 9 -12))
2160

It is not correct, as one commenter suggested, to sort all three arrays, sort the six-element array built as the first and last item from each sorted array, and then take either the three maximum items or the maximum plus two minimum items from the six-element array, as that does not require all three elements to come from three different arrays.

You can run the program https://ideone.com/GxKajf.

Advertisements

Pages: 1 2

8 Responses to “Maximum Product”

  1. Zack said

    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

    for i = 1:na
        a = A[ind_a[i]]
    
        for j = 1:nb
            b = B[ind_b[j]]
    
            for k = 1:nc
                c = C[ind_c[k]]
                p = a*b*c
    
                if p > mp
                    mp = p
                    Z[1] = a
                    Z[2] = b
                    Z[3] = c
                    counter = 0
                else
                    counter += 1
                end
    
                if counter >= iwp; return mp, Z, counter; end
            end
        end
    end
    
    return mp, Z, counter
    

    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!

  2. chaw said

    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)
    

  3. James Curtis-Smith said

    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];
    
  4. Paul said

    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)))
    
  5. chaw said

    @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.

  6. Zack said

    @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

  7. Bill Wood said

    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

  8. Daniel said

    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:

    $ ./a.out 10 -10 15 -2 . 10 -12 12 -2 . -11 -10 9 -12
    2160
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: