第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
1043. 分隔数组以得到最大和
题目地址(1043. 分隔数组以得到最大和)
题目描述
1
给你一个整数数组 arr，请你将该数组分隔为长度最多为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
2
3
返回将数组分隔变换后能够得到的元素最大和。
4
5
6
7
注意，原数组和分隔后的数组对应顺序应当一致，也就是说，你只能选择分隔数组的位置而不能调整数组中的顺序。
8
9
10
11
示例 1：
12
13
输入：arr = [1,15,7,9,2,5,10], k = 3
14
输出：84
15
解释：
16
因为 k=3 可以分隔成 [1,15,7] [9] [2,5,10]，结果为 [15,15,15,9,10,10,10]，和为 84，是该数组所有分隔变换后元素总和最大的。
17
若是分隔成 [1] [15,7,9] [2,5,10]，结果就是 [1, 15, 15, 15, 10, 10, 10] 但这种分隔方式的元素总和（76）小于上一种。
18
19
示例 2：
20
21
输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
22
输出：83
23
24
25
示例 3：
26
27
输入：arr = [1], k = 1
28
输出：1
29
30
31
32
33
提示：
34
35
1 <= arr.length <= 500
36
0 <= arr[i] <= 109
37
1 <= k <= arr.length
Copied!
前置知识
- 动态规划
- 记忆化递归
公司
- 暂无
记忆化递归
思路
这道题的思路无非就是暴力枚举所有的可能，求所有可能中的最大值即可。
因此我们可以枚举所有的 i，然后计算区间 [i:j] 的可能区间和，其中 j 的取值范围是 [i:i+k]。如何对区间求和呢？ 其实也容易，只需要用一个变量 max_ele 记录区间最大值（这在遍历的时候可以同时取得），然后 max_ele * (j-i+1) 即可，其中 j - i + 1 为区间的长度。这样我们就算出了区间 [i:i+k] 的区间和最大值。也就是说我们将问题规模缩小了，继续使用同样的方法直到问题缩小到寻常即可。使用递归可以轻松达到这一点。
代码
- 语言支持：Python3
Python3 Code:
1
class Solution:
2
def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
3
@lru_cache(None)
4
def dp(i):
5
if i >= len(arr): return 0
6
ans = 0
7
max_value = -1
8
for steps in range(1, k + 1):
9
if i + steps - 1 < len(arr): max_value = max(max_value, arr[i + steps - 1])
10
else: break
11
ans = max(ans, max_value * steps + dp(i + steps))
12
return ans
13
return dp(0)
Copied!
复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n)$
动态规划
思路
同上。我们可以将上面的代码改成普通 dp 形式。
只要：
- 将递归的代码改成 for 循环
- 记忆化的地方用 dp 数组代替
即可轻松实现。
代码
- 语言支持：Python3
Python3 Code:
1
class Solution:
2
def maxSumAfterPartitioning(self, nums: List[int], k: int) -> int:
3
n = len(nums)
4
dp = [0] * (n+1)
5
6
for i in range(1, n+1):
7
max_ele = 0
8
for j in range(i, min(n+1, i+k)):
9
max_ele = max(max_ele, nums[j-1])
10
# range: [i,j]
11
dp[j] = max(dp[j], (j-i+1) * max_ele + dp[i-1])
12
return max(dp)
Copied!
复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n)$
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago