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 位有符号整数。

自建示例

长段的最大值可以提升多个位置:

输入: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。