Here is program in OCaml, which is probably incomprehensible.
Code:
let id x = x
(*
ns : list of numbers (int)
len_ns : length of ns
os : list of binary operators of type int -> int -> int
len_os : length of os
op : the result accumulated so far of type int -> int
e.g. if ns = [1; 3; 2; 1; 4] and os = [(*); (+)],
and we select 1, then op = (1 * ...) that expects the second argument
cm : current maximum (maximum so far)
*)
let rec maximize ns len_ns os len_os op cm =
match (ns, os) with
| ([n], []) -> max cm (op n)
| (n :: ns', []) ->
let cm' = maximize ns' (len_ns - 1) [] 0 op cm (* skip n *) in
max cm' (op n) (* pick n *)
| (n :: ns', o :: os') ->
if len_ns > len_os + 1 then
let cm' = (maximize ns' (len_ns - 1) os len_os op cm) (* skip n *) in
maximize ns' (len_ns - 1) os' (len_os - 1) (o (op n)) cm' (* pick n and o *)
else maximize ns' (len_ns - 1) os' (len_os - 1) (o (op n)) cm
let run ns os =
maximize (rev ns) (length ns) (rev os) (length os) id 0
First, the program calculates left-to-right; so the first thing the main function "run" do is reverse the lists.
Consider a situation in the middle of the search. Suppose the initial (reversed) lists are [4; 1; 2; 3; 1] and [(+); (*)]. Suppose we skipped 4 and picked 1. Then the current expression is (1 * ...), which expects the second argument. This function that takes the next picked number and returns the result of the expression so far is the argument "op" of "maximize". The remaining lists at this point are [2; 3; 1] and [(*)]. Since the length of [2; 3; 1] is greater than the length of [(*)] by 2 (not by 1), we have a choice whether to pick 2. If we pick 2 and (*), then (after the recursive call) "op" becomes ((1 + 2) * ...) and we remove the heads of the lists "ns" and "os". If we don't pick n, then "op" stays the same and we remove the head of "ns" only.
The last argument "cm" of "maximize" is the maximum that is found so far. When we have a choice whether to pick the next number, we first feed "cm" to the recursive call that skips the number. It returns the maximum cm' that is obtained by exploring that part of the search tree. Then we feed cm' to the recursive call that picks the next number, and it returns the final maximum.