Expressió aritmètica màxima X62753

Donada una seqüència de n nombres reals positius x₀, x₁, …, x_n−1, considerem les expressions aritmètiques que es poden formar amb sumes i productes usant tots aquests nombres (potser afegint parèntesis) sense canviar-ne l’ordre relatiu.

Per exemple, si n=4 i la seqüència és (0.1, 2.5, 3.0, 2.2), aleshores algunes d’aquestes expressions són (ometem els parèntesis quan és possible per llegibilitat):

El nostre objectiu és calcular el nombre més gran que es pot obtenir avaluant aquestes expressions. Per exemple, si la seqüència és (2, 3, 4), aquest nombre és 24 i s’obté amb l’expressió 2 × 3 × 4. Si en canvi la seqüència és (0.1, 2.5, 3, 2.2), aleshores el màxim és 17.16 i s’obté amb (0.1+2.5) × 3 × 2.2.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, seguit de x₀, x₁, …, x_n−1. Podeu assumir que n ≥ 1 i que x_i > 0.

Sortida

Per cada cas, escriviu amb quatre dígits decimals el nombre més gran que es pot obtenir avaluant les expressions que es poden formar amb sumes i productes i tots els nombres x₀, x₁, …, x_n−1 sense canviar-ne l’ordre relatiu.

Observació

Resoleu aquest problema amb programació dinàmica.

Per escriure un double amb quatre dígits decimals podeu fer-ho així:

int main() {
  cout.setf(ios::fixed);
  cout.precision(4);
  double x;
  ...
  cout << x << endl;