题目描述 [分隔数组以得到最大和]
给出整数数组 A，将该数组分隔为长度最多为 K 的几个（连续）子数组。分隔完成后，每个子数组的中的值都会变为该子数组中的最大值。
返回给定数组完成分隔后的最大和。
示例
输入：A = [1,15,7,9,2,5,10], K = 3
输出：84
解释：A 变为 [15,15,15,9,10,10,10]
解题思路
动态规划
- 定义dp[i]为子数组A[0,j]按照题意分割后的最大和
- 定义最后一个分割区间长度j， 则显然 j∈[1,K]
- 定义最后一个分割区间最大值 num_max， 则有num_max=max{num_max, A[i−j+1,i]}
- 对于每种取值，均可更新最优解，因此转移公式为：
dp[i] = max(dp[i], dp[i-j] + j * num_max) i - j >= 0
dp[i] = max(dp[i], j * num_max) , else
代码
class Solution {
public:
int maxSumAfterPartitioning(vector<int>& A, int K) {
vector<int> dp(A.size());
for(int i=0;i<A.size();i++){
int max_num = A[i];
for(int j=1;j<=K&&i-j+1>=0;j++){
max_num = max(max_num, A[i-j+1]);
if(i-j>=0) dp[i] = max(dp[i], dp[i-j]+j*max_num);
else dp[i] = max(dp[i], j*max_num);
}
}
return dp[A.size()-1];
}
};
