Изменения

Данная задача решается с использованием принципа оптимальности на подотрезке. Введём матрицу <tex>d</tex> размером <tex>n \times n</tex>, где <tex>d[i][j]</tex> будет равен максимальному значению, достигаемому на подотрезке <tex dpi = "130">a_i, a_{i+1}, \dots, a_j</tex>.

Получаем следующие соотношения: <br />

* <math>d[i][j] = \max_{\mathop{k = i..j-1}}[\max(d[i][k]+d[k+1][j], d[i][k]*d[k+1][j])] \ (i < j)</math> <br />

Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.