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
方法:动态规划,以 i 结尾时(即 arr[0...i])分割后的最大和 = 最后一段子数组[j...i]的最大和 + 前面[0...j-1]的最大分割和。
class Solution { public int maxSumAfterPartitioning(int[] arr, int k) { int n = arr.length; // 设 d[i] 为以 i 结尾时(即 arr[0...i])分割后的最大和,最后只需要返回 dp[n-1] int[] dp = new int[n]; // 递推,i 是结束位置 for (int i = 0; i < n; ++i) { // 倒序枚举最后一个子数组的起点,[j...i] 长度不能k // 在倒序枚举j的过程中 更新 max,得到 arr[j...i]内的最大值 int max = arr[i]; // 1 <= len([j...i] = i-j+1) <= k for (int j = i; j >= Math.max(i - k + 1, 0); --j) { // 当前 arr[j...i] 内最大值 max = Math.max(max, arr[j]); // 为以 i 结尾时(即 arr[0...i])分割后的最大和 = 最后一段子数组[j...i]的最大和 + 前面[0...j-1]的最大分割和 // 注意不要越界 dp[i] = Math.max(dp[i], (j > 0 ? dp[j - 1] : 0) + (i - j + 1) * max); } } // 返回 return dp[n - 1]; } }
标签:1043,...,arr,分隔,05,int,max,数组,dp From: https://www.cnblogs.com/fulaien/p/17334906.html