# 1043. 分隔数组以得到最大和
### 题目地址(1043. 分隔数组以得到最大和)
### 题目描述
```
给你一个整数数组 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:
```python
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:
```python
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)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1043.partition-array-for-maximum-sum.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.