题意：
给出整数数组A，将该数组分隔为长度最多为K的几个（连续）子数组。分隔完成后，每个子数组的中的值都会变为该子数组中的最大值。
返回给定数组完成分隔后的最大和。
示例：
输入：A = [1,15,7,9,2,5,10], K = 3
输出：84
解释：A 变为 [15,15,15,9,10,10,10]
思路：
简单DP。dp[i]表示分割完前i个数，最大值是多少。
j表示当前段的长度[1,K]。
假设我们知道[i-j,i]这一段的最大值curMax，那么dp[i]可以从dp[i-j]推过来。
dp[i] = max(dp[i],dp[i-j]+curMax*j);
curMax又可以通过遍历j的时候来更新。
1 class Solution { 2 public: 3 int maxSumAfterPartitioning(vector<int>& A, int K) { 4 int l=A.size(); 5 vector<int>dp(l+1,0); 6 for(int i=1;i<=l;i++){ 7 int ma=0; 8 for(int j=1;j<=K&&i-j>=0;j++){ 9 ma=max(ma,A[i-j]); 10 dp[i]=max(dp[i],dp[i-j]+ma*j); 11 if(i==4)cout<<dp[i-j]<<‘ ‘<<ma<<endl; 12 } 13 } 14 return dp[l]; 15 } 16 };
原文：https://www.cnblogs.com/ljy08163268/p/11723633.html
