leetcode 1043. Partition Array for Maximum Sum
题意：分割一个数组，保证分割的每个段最多K个数，将每个段的每个数换成当前段最大的那个数，求最终的最大值。
思路：简单DP。dp[i]表示分割完前i个数，最大值是多少。
j表示当前段的长度[1,K]。
假设我们知道[i-j,i]这一段的最大值curMax，那么dp[i]可以从dp[i-j]推过来。
dp[i] = max(dp[i],(i>=K?dp[i-j]:0)+curMax*j);
curMax又可以通过遍历j的时候来更新。
class Solution {
public:int maxSumAfterPartitioning(vector<int>& A, int K) {int n = A.size();vector<int> dp(n,0);for(int i=0;i<A.size();i++){int curMax = 0;for(int j=1;j<=K && i-j+1>=0;j++){curMax = max(curMax,A[i-j+1]);dp[i] = max(dp[i],(i>=K?dp[i-j]:0)+curMax*j);}}return dp[n-1];}
};