题目描述 [分隔数组以得到最大和]

给出整数数组 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];
    }
};