1043. 分隔数组以得到最大和【leetcode】/动态规划

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

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

给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

示例 1：
输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]

示例 2：
输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83

示例 3：
输入：arr = [1], k = 1
输出：1

提示：
1 <= arr.length <= 500
0 <= arr[i] <= 109
1 <= k <= arr.length

动态规划

dp[i]表示到第i个数得到的最大和，每次先令第i个元素单独为一组，再令它和前面一个为一组…直到它和前面k-1个为一组，取最大的

class Solution {
public:int maxSumAfterPartitioning(vector<int>& arr, int k) {if(k==0) return 0;int dp[505];memset(dp,0,sizeof(dp));int len=arr.size();dp[0]=arr[0];for(int i=1;i<len;i++){//表示选择的数中的最大值int maxn=arr[i];for(int j=i;j>=i-k+1&&j>=0;j--){maxn=max(maxn,arr[j]);(j==0)?dp[i]=max(dp[i],maxn*(i-j+1)):dp[i]=max(dp[i],dp[j-1]+maxn*(i-j+1));}}return dp[len-1];}
};

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

---