优化O(n^2)算法O(n log n).
问题陈述
考虑到阵列A的n正整数.将数组划分为长度不大于连续子序列,k使得每个子序列的最大值之和最小.这是一个例子.
如果n = 8和,k = 5和数组的元素1 4 1 3 4 7 2 2,最好的解决方案是1 | 4 1 3 4 7 | 2 2.总和将是max{1} + max{4, 1, 3, 4, 7} + max{2, 2} = 1 + 7 + 2 = 10.
O(n ^ 2)解
我们dp[i]是最低金额为问题语句子问题阵列A[0] ... A[i].dp[0] = A[0]而且,对于0 < i …