class Solution {
public:
int maxSumAfterPartitioning(vector<int>& arr, int k) {
}
};
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 <= 5000 <= arr[i] <= 1091 <= k <= arr.length原站题解
python3 解法, 执行用时: 1100 ms, 内存消耗: 46.3 MB, 提交时间: 2022-11-25 16:56:44
class Solution:
def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
N, ans, n = 505, 0, len(arr)
mp = [[-1 for i in range(N)] for i in range(N)]
def dfs(u: int, Max: int, v: int) -> int:
if mp[u][v] != -1:
return mp[u][v]
if u == n:
return v * Max
res = Max * v + dfs(u+1, arr[u], 1)
if v + 1 <= k:
res = max(res, dfs(u+1, max(Max, arr[u]), v+1))
mp[u][v] = res
return res
return dfs(1, arr[0], 1)
python3 解法, 执行用时: 908 ms, 内存消耗: 15 MB, 提交时间: 2022-11-25 16:53:35
'''
dp[i] 代表前i项元素最大和
1. 先求解前 k 项的和的最大值，作为动态规划的初始条件
2. dp[i] = dp[i-j-1] + 区间 [i-j, i+1) 最大值 * 区间长度组成
3. 条件转移方程为: dp[i] = dp[i-j-1] + max(arr[(i-j):(i+1)]) * (j+1)
'''
class Solution:
def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
n = len(arr)
dp = [0]*n
for i in range(k):
dp[i] = max(arr[:i+1])*(i+1)
for i in range(k,n):
dp[i] = max(dp[i-j-1] + max(arr[(i-j):(i+1)]) * (j+1) for j in range(k))
return dp[-1]