решение за куб:

dp[i][j] = max(dp[k][i-1] + sum(k..i-1)*sum(i..j))

тогда решение за n^2 можно получить, перебирая i и для каждого i сделать конвекс хул трик,

добавив прямые sum(k..i-1) * x + dp[k][i-1],

тогда перебираем j и сделаем запрос к нашей выпуклой оболочке с x = sum(i..j)

тогда dp[i][j] как раз будет максимум по dp[k][i-1] + sum(k..i-1)*sum(i..j)

Let dp[n][len] be the maximum value I can get with the first n elements of the sequence if the length of the last block is len. It is easy to see the formula dp[n][len] = min_k(dp[n - len][k] + (s_n - s_n - len) × (s_n - len - s_{n - len - k}) where s_i is the accumulative sum of the first i elements. Now dp[n][k] = min_k(dp[n - len][k] + (s_n - s_n - len)s_n - len - (s_n - s_n - len)s_{n - len - k} dp[n][k] = min_k(dp[n - len][k] - (s_n - s_n - len)s_{n - len - k})) + (s_n - s_n - len)s_n - len the first part can be calculated using convex hull trick, the complexity will be

In your question it is not clear whether you are given k or not. If you are not given k the solution provided by jcg will be correct. If you are given k the problem can be solved using the approach described here and here in . But it can be further optimised to , because we can do convex hull (which we actually use inside the binary search) in O(1) time using a stack.