1043. 分隔数组以得到最大和
关键词：动态规划、递归
题目来源：1043. 分隔数组以得到最大和 - 力扣（Leetcode）
题目描述
T动态规划
T递归
给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。
输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83
输入：arr = [1], k = 1
输出：1
数据范围
1 <= arr.length <= 500
0 <= arr[i] <= 109
1 <= k <= arr.length
问题分析
很容易发现，当确定第一个子数组后，剩下的便是一个与原问题相似的子问题，于是便得到如下朴素解法。
朴素递归
第一个子数组的起点已知，为i（当前问题的第一个子数组的起点为0），枚举第一个子数组的终点j，注意区间长度不能超过k，于是第一个子数组就为[i, j]，也即有如下等式
dfs(i) = max( (i-j+1)*maxV + dfs(j+1) )
其中，dfs(i)表示第一个子数组起点为i时的最大和，dfs(0) 便是最终结果。
解空间可近似看做一棵高度为n的k叉树，所以时间复杂度为O(k^n)，空间复杂度为O(n)。
记忆化
考虑到递归过程存在许多重复计算，因此可采用记忆化搜索，使用f[i]来记录dfs(i)的结果。
对于每个i，只有f[i]还没计算过时，才会分叉计算，一共分成k叉，于是时间复杂度为O(nk)，空间复杂度为O(n)。
动态规划
至此，已经有动态规划的雏形了。递归的时候，i在“递”时是从小到大，“归”时是从大到小，于是，动态规划中的第一层for循环的i便与“归”保持一致，第二层for循环同样是枚举第一个子数组终点。
动态规划的时间复杂度为O(nk)，空间复杂度为O(n)。
以上动态规划的思路是从递归转换而来，如果不借助递归，我们可以按如下来思考。
第一个子数组的起点已经确定，只需确定第一个子数组的终点就可完全确定第一个子数组。一旦第一个子数组的终点确定，第二个子数组的起点就确定，只需确定第二个子数组的终点就可以完全确定第二个子数组。依次类推。
由于最后一个子数组的终点也是确定的，于是，可以从前往后枚举每一个起点i，f[i]表示第一个数组起点为i时的最大和，于是f[0]便是题目所求答案。
空间优化
由于本题的n不超过500，所以此步并不是很重要，但这种思路需要注意。
在动态规划中，计算f[i]时，只会用到f[i..i+k+1]共k+1个位置，在计算f[i-1]时，只会用到f[i-1..i+k]共k+1个位置，可以发现，每次用到的位置会后移，于是可采用一个滚动数组来优化空间，用f[i%k]来代替法f[i]，但要注意，i与i+k+1是同余的。空间复杂度为O(k)。
代码实现
朴素递归
int maxSumAfterPartitioning(vector<int> &arr, int k) {
int n = arr.size();
function<int(int)> dfs = [&](int i) {
int res = 0;
// 枚举当前问题的第一个子数组的终点
for (int j = i, maxV = 0; j < i + k && j < n; j++) {
maxV = max(arr[j], maxV);
res = max(dfs(j + 1) + (j - i + 1) * maxV, res);
}
return res;
};
return dfs(0);
}
记忆化
int maxSumAfterPartitioning(vector<int> &arr, int k) {
int n = arr.size(), f[n];
memset(f, -1, sizeof(f));
function<int(int)> dfs = [&](int i) {
if (i >= n)return 0;
int &res = f[i];
if (res != -1)return res;
// 枚举当前问题的第一个子数组的终点
for (int j = i, maxV = 0; j < i + k && j < n; j++) {
maxV = max(arr[j], maxV);
res = max(dfs(j + 1) + (j - i + 1) * maxV, res);
}
return res;
};
return dfs(0);
}
动态规划
int maxSumAfterPartitioning(vector<int> &arr, int k) {
int n = arr.size(), f[n + 1];
memset(f, 0, sizeof f);
for (int i = n - 1; i >= 0; i--) {
// 枚举当前问题的第一个子数组的终点
for (int j = i, maxV = 0; j < i + k && j < n; j++) {
maxV = max(arr[j], maxV);
f[i] = max(f[j + 1] + (j - i + 1) * maxV, f[i]);
}
}
return f[0];
}
空间优化
int maxSumAfterPartitioning(vector<int> &arr, int k) {
int n = arr.size(), f[k];
memset(f, 0, sizeof f);
for (int i = n - 1; i >= 0; i--) {
// 由于i和i+k+1同余k，所以在计算过程中不能直接覆盖
int res = 0;
// 枚举当前问题的第一个子数组的终点
for (int j = i, maxV = 0; j < i + k && j < n; j++) {
maxV = max(arr[j], maxV);
res = max(f[(j + 1) % k] + (j - i + 1) * maxV, res);
}
f[i % k] = res;
}
return f[0];
}