Building an expression with maximum value

Programmer Question

Given n integers, is there an O(n) or O(n log n) algorithm that can compute the maximum value of a mathematical expression that can be obtained by inserting the operators -, +, * and parentheses between the given numbers? Assume only binary variants of the operators, so no unary minus, except before the first element if needed.

For example, given -3 -4 5, we can build the expression (-3) * (-4) * 5, whose value is 60, and maximum possible.

Background:

I stumbled upon this problem some time ago when studying genetic algorithms, and learned that it can be solved pretty simply with a classical genetic algorithm. This runs slowly however, and it's only simple in theory, as the code gets rather ugly in practice (evaluate the expression, check for correct placement of brackets etc.). What's more, we're not guaranteed to find the absolute maximum either.

All these shortcomings of genetic algorithms got me wondering: since we can don't have to worry about division, is there a way to do this efficiently with a more classic approach, such as dynamic programming or a greedy strategy?

Find the answer here