Решение

Пусть задано некоторое алгебраическое выражение, содержащее N чисел. Рассмотрим кусок этого выражения, расположенный между i-м и j-м его числами включительно (1 ≤ i ≤ j ≤ N). Пусть Max(i, j) обозначает максимально возможное после расстановки скобок значение этого куска, а Min(i, j) – минимально возможное. Эти числа следует вычислять парами в порядке увеличения длин кусков j-i+1. Ясно, что для всех i от 1 до N значения Max(i, i) и Min(i, i) совпадают и равны i-му числу выражения. При i < j число Max(i, j) вычисляем следующим образом. Перебираем все значения k, такие что i ≤ k < j, и каждый раз предполагаем, что при вычислении значения рассматриваемого куска самой последней выполняется операция, записанная между числами с номерами k и k+1. Если это, к примеру, операция вычитания, то чтобы максимизировать значение части выражения от i-го числа до j-го, мы должны взять максимальное значение куска от i-го числа до k-го (которое уже вычислено) и вычесть из него минимальное значение куска от (k+1)-го числа до j-го (которое также уже вычислено). Из значений, полученных при анализе различных k, выбираем максимальное. Операции + и * и вычисление Min(i, j) рассматриваются аналогично.