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