1043. Partition Array for Maximum Sum ===================================== 题目信息 -------- :题号: 1043 :难度: Medium :主题: 数组分段、区间最大值、最大化总和 :原题: `LeetCode 1043 `_ :重点: 把整个数组划分为连续非空段,每段长度至多 ``k``;段内所有元素都替换为该段原始最大值后求最大总和 题目重述 -------- 给定整数数组 ``arr`` 和整数 ``k``。需要按原顺序把整个数组划分成若干连续且非空的子数组,每个子数组长度不能超过 ``k``。 对于每个分段,把其中每个元素都替换为该段在替换前的最大值。完成所有分段和替换后,返回新数组元素总和能够达到的最大值。 ``1 <= arr.length <= 500``,``0 <= arr[i] <= 10^9``,``1 <= k <= arr.length``;题目保证答案适合 32 位有符号整数。 自建示例 -------- 长段的最大值可以提升多个位置: .. code-block:: text 输入:arr = [2,1,7,3,4], k = 3 输出:29 解释:分成 [2,1,7] 和 [3,4],替换后得到 [7,7,7,4,4],总和为 29。 每段最多只能包含一个元素: .. code-block:: text 输入:arr = [3,1], k = 1 输出:4 解释:每个元素必须单独成段,替换不会改变数组,总和仍为 3 + 1 = 4。