Links

1043. 分隔数组以得到最大和

题目地址(1043. 分隔数组以得到最大和)

https://leetcode-cn.com/problems/partition-array-for-maximum-sum/

题目描述

给你一个整数数组 arr,请你将该数组分隔为长度最多为 k 的一些(连续)子数组。分隔完成后,每个子数组的中的所有值都会变为该子数组中的最大值。
返回将数组分隔变换后能够得到的元素最大和。
 
注意,原数组和分隔后的数组对应顺序应当一致,也就是说,你只能选择分隔数组的位置而不能调整数组中的顺序。
 
示例 1:
输入:arr = [1,15,7,9,2,5,10], k = 3
输出:84
解释:
因为 k=3 可以分隔成 [1,15,7] [9] [2,5,10],结果为 [15,15,15,9,10,10,10],和为 84,是该数组所有分隔变换后元素总和最大的。
若是分隔成 [1] [15,7,9] [2,5,10],结果就是 [1, 15, 15, 15, 10, 10, 10] 但这种分隔方式的元素总和(76)小于上一种。
示例 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,15,7,9,2,5,10],k=3 第一次我们可以选择 [1] 或者 [1,15] 或者[1,15,7]。根据题意,将子数组内的元素变成子数组的最大值。也就是变为 [1] 或者 [15, 15] 或者 [15,15,15]。
去掉这段子数组,例如去掉 [1,15,7],剩余的要解决的问题是 [9,2,5,10]。这是一个和原问题完全一样但是规模更小的子问题,所以可以用递归解决。
具体来说:
  • 我们可以枚举所有的 i,然后计算区间 [i:j] 的区间和,其中 j 的取值范围是 [i:i+k]。
当我们求出来的时候, 就继续使用同样的方法计算剩下子数组的区间和,并将其加起来就是答案。也就是说我们将问题规模缩小了,继续使用同样的方法直到问题缩小到寻常即可。使用递归可以轻松达到这一点。
  • 如何对区间求和呢? 其实也容易,只需要用一个变量 max_ele 记录区间最大值(这在遍历的时候可以同时取得),然后当前区间对答案的贡献就是 max_ele * (j-i+1) ,其中 j - i + 1 为区间的长度。
  • 这样我们就算出了区间 [i:j] 的区间和。 这 k 种分割区间的方式([i:i+1], [i:i+2]...[i:i+k])的最大值就是我们想要找的子问题答案。

代码

  • 语言支持:Python3
Python3 Code:
class Solution:
def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
@lru_cache(None)
def dp(i):
if i >= len(arr): return 0
ans = 0
max_value = -1
for steps in range(1, k + 1):
if i + steps - 1 < len(arr): max_value = max(max_value, arr[i + steps - 1])
else: break
ans = max(ans, max_value * steps + dp(i + steps))
return ans
return dp(0)
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n * k)$
  • 空间复杂度:$O(n)$

动态规划

思路

同上。我们可以将上面的代码改成普通 dp 形式。
只要:
  • 将递归的代码改成 for 循环
  • 记忆化的地方用 dp 数组代替
即可轻松实现。

代码

  • 语言支持:Python3
Python3 Code:
class Solution:
def maxSumAfterPartitioning(self, nums: List[int], k: int) -> int:
n = len(nums)
dp = [0] * (n+1)
for i in range(1, n+1):
max_ele = 0
for j in range(i, min(n+1, i+k)):
max_ele = max(max_ele, nums[j-1])
# range: [i,j]
dp[j] = max(dp[j], (j-i+1) * max_ele + dp[i-1])
return max(dp)
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n * k)$
  • 空间复杂度:$O(n)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。