Алгоритм заключения выражения в скобки, чтобы максимизировать его значение

Я обнаружил это при поиске задач по динамическому программированию. Вам дано выражение без скобок в форме V0 O0 V1 O1 .. .. Vn-1

Мы должны поставить скобки в местах, которые максимизируют значение всего выражения.

V - это операнды, а O - операторы. В первой версии задачи операторы могут быть * и +, а операнды положительны. Вторая версия задачи является полностью общей.

Для первой версии я предложил решение DP.

Решение - A [] = массив операндов B [] - массив операторов T (A [i, j]) - максимальное значение выражения {{1} } T (A [0, n-1]) = max по всем i {(T (A [0, i]) Oi T (A [i + 1, n-1]))}

Граничные случаи тривиальны (когда i = j). Мне нужна помощь в следующем - Анализировать время работы этого алгоритма. И если есть лучший.