1043. 分隔数组以得到最大和

本文主要是介绍1043. 分隔数组以得到最大和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出整数数组 A，将该数组分隔为长度最多为 K 的几个（连续）子数组。分隔完成后，每个子数组的中的值都会变为该子数组中的最大值。

返回给定数组完成分隔后的最大和。

 

示例：

输入：A = [1,15,7,9,2,5,10], K = 3
输出：84
解释：A 变为 [15,15,15,9,10,10,10]

 

提示：

1. 1 <= K <= A.length <= 500
2. 0 <= A[i] <= 10^6

思路：动态规划，dp[i]表示前i+1个数的最大和,

dp[i]=max(dp[j]+ max(A[i-j : i]) *j )，其中A[i-j : i]这一段数组，是指A[i], A[i-1]……A[i-K+1]最多K个数，即A[i-j], j=[0, K-1]

class Solution {
public:int maxSumAfterPartitioning(vector<int>& A, int K) {vector<int>dp(A.size());for(int i=0; i<A.size(); ++i){int cur=0;for(int j=1; j<=K && i-j+1>=0; ++j){cur=max(cur, A[i-j+1]);//不断地找到区间[A[i-j+1], A[i]]的最大值，区间长度为j，区间长度最大为K，j最大取Kdp[i]=max(dp[i], (i-j>=0 ? dp[i-j] :0)+cur*j);//前i+1个数的最大和=前i-j+1个数的最大和+区间最大值*区间长度}}return dp.back();}
};

 

这篇关于1043. 分隔数组以得到最大和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---