目录

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

相似问题:

分析

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

解答

 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