Защитный барьер

Будем решать задачу с помощью метода динамического программирования.

$$$dp_{l, r}$$$ будет означать множество множеств возможных коэффициентов, которые стоят при числах. (Коэффициент означет, сколько раз мы прибавили это число к ответу).

Переберем позицию максимума, тогда мы точно знаем какой при этом числе стоит коэффициент (количество отрезков, которые содержат этот элемент), а также знаем, какие отрезки пойдут влево и вправо, и можем пересчитать динамику перебрав коэфиценты из $$$dp_{l, m - 1}$$$ и $$$dp_{m + 1, r}$$$.

Чтобы найти ответ, не нужно знать порядок коэффициентов в массиве, поэтому количество различных состояний динамики ограничено количеством разбиений $$$m$$$ на слагаемые (а более точно, количеством разбиений количества отрезков, целиком лежащих внутри состояния).

Таким образом время работы составит не более $$$O(n^3 \cdot P(m))$$$, но на самом деле гораздо меньше.