旅游景区网站建设的意义,如何选择做网站的公司,网站的开发语言,建筑网站招聘题目#xff1a; 给你一个整数数组 arr#xff0c;请你将该数组分隔为长度 最多 为 k 的一些#xff08;连续#xff09;子数组。分隔完成后#xff0c;每个子数组的中的所有值都会变为该子数组中的最大值。
返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试…题目 给你一个整数数组 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
来源力扣LeetCode 链接https://leetcode.cn/problems/partition-array-for-maximum-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
思路
首先要看样例来寻找灵感。
在推完前两个样例的时候应该就会发现规律。当你从前往后开始进行的时候每到一个位置都要进行判断是不是要以当前位置为核心开始赋值如果是最大值要向周围进行赋值的话是先前还是先后分别向前多少向后多少这些都是你要考虑的。
就以第二个例子为例i 从0到n-1开始进行判断 i 0的时候那肯定是1 、 i 1的时候发现4是向前k个数里最大的因此此时的最大值是4 整体的和就是8 i 2的时候发现k 个数内还是4是最大值因此整体的和就是12 i 3 的时候发现 k 个数内最大值是5 因此整体的和就是20 i 4 的时候发现 k 个数内最大值是7 但是k4所以最多只能向前赋值4个数和就是29 …
好的推到这里应该就有感觉了吧
没有那我让你有点感觉~
你会发现i 从前向后走的时候每走到一个新的值那以i 结尾的整体的和的最大值其实就是可以得到的也就是说当前位置的最终答案是可以根据之前得到的结果计算得到都说到这了还没有感觉么
这不就是状态转移方程嘛这不就是DP的感觉嘛
用dp【i】 来表示以 i 作为结尾元素的整体的最大和最后的答案就是dp【n-1】。
那状态转移方程就可以是 dp【i】 maxdp【i】( j 0 ? dp[j-1] : 0) res*i-j1
j 的含义是从 i 开始向前枚举 k 个位置 以为之前的每个位置的整体最大和是已经算过的也就是dp【0】到dp【i-1】都是计算过的那 j 从 i 开始向前枚举用arr【j】来更新 j 到 i 内的最大值res然后将res赋值到 j 到 i 的所有数dp【i】就取赋值之前和赋值之后的较大值。
通过这样的状态转移方程i 从 0 遍历到 n-1 最终的dp【n-1】就是要返回的答案
代码
class Solution {
public:int maxSumAfterPartitioning(vectorint arr, int k) {int n arr.size();int dp[510] {0};for(int i 0 ; i n ; i){int res arr[i];for(int j i ; j max(i-k1 , 0) ; j--){res max(res , arr[j]);dp[i] max(dp[i] , (j 0 ? dp[j-1] : 0) res*(i-j1));// cout i j res endl;// cout dp[i] endl;}}return dp[n-1];}
};
