Maximum of outer product of integer vectors (in linear time)

Question

Introduction

Our goal is to efficiently find the maximum of a large amount of (redundant) data.

We define the outer product of vectors \$A\$ and \$B\$ as a matrix containing the products of all entries of \$A\$ with each entry of \$B\$. (see outer Product)

$$ A\otimes B := A\cdot B^T = \left(\begin{array}{rrr} A(1)\cdot B(1) & A(1)\cdot B(2) & \ldots & A(1)\cdot B(M)\\ A(2)\cdot B(1) & A(2)\cdot B(2) & \ldots & A(2)\cdot B(M)\\ \ldots & & & \ldots \\ A(N)\cdot B(1) & A(N)\cdot B(2) & \ldots & A(N)\cdot B(M)\\ \end{array}\right) $$

Here \$A\$ has \$N\$ entries (size \$N\$) and \$B\$ has \$M\$ entries.

In this way, the outer product of \$K\$ vectors yields a \$K\$-dimensional array (tensor of order \$K\$). If \$N_1,N_2,\ldots,N_K\$ are the sizes of the vectors, we get a total of \$N_1\cdot N_2\cdot\ldots\cdot N_K\$ products.

Example: $$ \left(\begin{array}{r}1\\ 2\\ 0\end{array}\right)\otimes \left(\begin{array}{r}1\\ 3\end{array}\right)\otimes \left(\begin{array}{r}-5\\ 7\end{array}\right)= \left(\begin{array}{rr|rr|rr}-5 & 7 & -10 & 14 & 0 & 0\\ -15 & 21 & -30 & 42 & 0 & 0\end{array}\right) $$

The result is a \$3\$-dimensional array consisting of three \$2\times2\$ slices. We want to determine the maximum of the array, which is \$42\$ here.
An alternative formulation is: Find the maximum of all products that contain exactly one number from each vector.

Of course, we can do all the multiplications and keep track of the maximum. However, it is possible to use only a number of operations that depends linearly on the length of the input sequence (total number of vector entries). This means that we can, for example, process an input of \$13\$ vectors each of size \$37\$ in less than one second on a common computer.
Thus, the problem reads:

Challenge

• "Determine the maximum of the outer product of given integer-valued vectors. Ensure that the algorithm runs in linear time with respect to the length of the input sequence."
• The input contains at least one vector.
• This is code-golf, so shortest answer in bytes wins!

Test cases

We leave the input format to the free decision. In the test cases we use \$,\$ to separate vector entries and \$;\$ to separate vectors. So the example above is coded as: \$\quad 1,2,0;1,3;-5,7\$

• \$0,1,2\qquad ->\qquad 2\$
• \$-2,-1,-2;1,2,3;-1,-2\qquad ->\qquad 12\$
• \$-2,-1;-3,-4;-3,2,1;1,4,-4\qquad ->\qquad 96\$
• \$-1,-2;3,4\qquad ->\qquad -3\$
• \$-1,-2;1,-3,2;1,-1,-2\qquad ->\qquad 8\$
• \$1,0,-2;0,-2,1;-2,1,0;-2,0,1;0,1,-2;1,-2,0;1,0,-2;0,-2,1;-2,1,0;-2,0,1;0,1,-2;1,-2,0;1,0,-2;0,-2,1;-2,1,0;-2,0,1;0,1,-2;1,-2,0;1,0,-2;0,-2,1;-2,1,0;-2,0,1;0,1,-2;1,-2,0;1,0,-2;0,-2,1;-2,1,0;-2,0,1;0,1,-2;1,-2,0;1,-2,0;1,0,1\qquad ->\qquad 1073741824\$

Answer 1

JavaScript (Node.js), 84 bytes

f=([a,...x],m=1,n=1)=>a?f(x,Math.min(...q=a.flatMap(c=>[c*m,c*n])),Math.max(...q)):n

Try it online!

Keep trace of min and max

Answer 2

Jelly, 12 10 bytes

Ṃ,ṀƊ×þFɗ/Ṁ

Try it online!

-2 from using Ɗ and ɗ for grouping instead of separate lines

This submission is a monadic link. For input, use a list of the vectors (i.e. [[1,2,0],[1,3],[-5,7]]) as the first argument. This assumes [] is not valid input.

This is similar to @l4m2's algorithm, but it starts with the first vector instead of (1, 1).

Explanation:

This works by taking the (min, max) of the first vector and finding all products of either with elements of the second vector. The same thing happens with the result and the third vector, then that result and the fourth, etc. Then, the answer is the max of the last result.

Ṃ,ṀƊ×þFɗ/Ṁ
Ṃ          # List Minimum
 ,         # Pair
  Ṁ        # List Maximum
   Ɗ       # Group the last 3 links ("Ṃ", ",", and "Ṁ") as a monad
    ×þ     # Outer product
      F    # Flatten
       ɗ   # Group the last 3 links ("Ṃ,ṀƊ", "×þ", and "F") as a dyad
        /  # Reduce
         Ṁ # List Maximum

This is my first time using Jelly, so there is probably still room for further golfing.

Answer 3

Wolfram Language (Mathematica), 29 bytes

Max@*Fold[{#2Min@#,#2Max@#}&]

Try it online!

Answer 4

Python 3.8 (pre-release), 85 bytes

Port of @l4m2's JavaScript answer

f=lambda x,y=1,z=1:x and f(x[1:],min(q:=sum(([c*y,c*z]for c in x[0]),[])),max(q))or z

Try it online!

Answer 5

05AB1E, 11 10 bytes

1$vsß‚yδ*Z

Port of @EvanBailey's Jelly answer, which in turn uses the same approach as @l4m2's Javascript answer, so make sure to upvote both of them as well!

Input as a list of lists.

Try it online or verify all test cases (with brute-force verify .»â€˜Pà in the footer for the smaller test cases).

Explanation:

1           # Push 1
 $          # Push another 1, and the input-list
  v         # Pop the input-list, and loop over each inner list `y`:
   s        #  Swap so the current list is at the top
            #  (or simply swap the two 1s on the stack in the very first iteration)
    ß       #  Pop and push the minimum (1 remains 1)
     ‚      #  Pair the top two values together
            #  ([1,1] in the first iteration; [max,min] in every other iteration)
       δ    #  Apply double-vectorized
      y     #  on this pair and list `y`:
        *   #   Multiply
         Z  #  Push the flattened maximum (without popping the list of lists)
            # (after the loop, the final flattened maximum that's on top of the stack is
            # output implicitly as result)

It runs in \$O(\sum L)\$, where \$L\$ is the length of each individual list.

In term of iterations, it'll do \$\sum(6L)-2L_n\$, where \$6\$ comes from \$2\$ (for \$[min,max]\$) times \$3\$ (once for the double-vectorized to create the list; and then once each to retrieve the flattened maximum and minimum of this list of lists); minus \$2\$ times the length of the last list \$L_n\$, since we won't retrieve its minimum. E.g. input [[1,2,0],[1,3],[-5,7]] has \$6\times3+6\times2+6\times2-2\times2=38\$ iterations and an input of \$13\$ lists of size \$37\$ each has \$13\times6\times37-2\times37=2812\$ iterations.

Answer 6

Charcoal, 19 bytes

⊞υ¹ＦＡ≔⁺×ι⌊υ×ι⌈υυＩ⌈υ

Try it online! Link is to verbose version of code. Explanation: Another port of @l4m2's algorithm.

⊞υ¹

Start with a minimum and maximum of 1.

ＦＡ

Loop over the input vectors.

≔⁺×ι⌊υ×ι⌈υυ

Multiply the current vector by both the minimum and maximum so far.

Ｉ⌈υ

Output the final maximum.

Answer 7

Haskell, 80 bytes

r a=[minimum a,maximum a]
f=last.foldl1(\a b->r$map product$sequence[a,b]).map r

Try it online!

Answer 8

Haskell, 50 bytes

m.foldl1(\x->((*)<$>[minimum x,m x]<*>))
m=maximum

Attempt This Online!

-2 bytes thanks to @ Unrelated String.

A port of my Mathematica answer.

Answer 9

Vyxal 14 11 bytes

?ƒλ₍gGẊvΠ;G

Try it online!

Any improves welcome! For input needs always list of vectors,
so first test case should be [[0,1,2]]

Explanation

?      # Get input
ƒ      # Begin reduce list of vectors by lambda
λ      # Open lambda
₍gG    # [min, max] of current vector
Ẋ      # Cartesian product with previous vector
vΠ     # Vectorised product
;G     # Close lambda and print total max

Answer 10

R, 42 bytes

function(L)max(Reduce(`%o%`,Map(range,L)))

Try it online!

Using outer instead of '%o%' is equivalent. Fortunately, range returns a vector of c(min,max) instead of max - min as you might otherwise expect. Based, as many others, on l4m2's answer

Also, random note, range automatically flattens lists.