1043：分隔数组以得到最大和（1916 分）

力扣第 136 场周赛第 3 题

题目

给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

示例 1：

输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]

示例 2：

输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83

示例 3：

输入：arr = [1], k = 1
输出：1

提示：

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 109
• 1 <= k <= arr.length

相似问题：

• 2098：长度为 K 的最大偶数和子序列
• 2767：将字符串分割为最少的美丽子字符串（1864 分）
• 3144：分割字符频率相等的最少子字符串（1917 分）

分析

按第一段分几个即可递推，注意该段的最大值也可递推。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
	@cache
	def dfs(i):
		res, ma = 0, 0
		for j in range(i,min(i+k,n)):
			ma = max(ma,arr[j])
			res = max(res,ma*(j-i+1)+dfs(j+1))
		return res
	
	n = len(arr)
	return dfs(0)

352 ms