1043. 分隔数组得到最大和主题描述
给定一个整数数组 arr 和一个整数 k,最多将这个数组分成长度 k 一些连续子数组。分离后,每个子数组的所有值都将成为该子数组的最大值。
将数组分离转换后能得到的最大元素和返回。
- 示例
input : arr = [1, 15, 7, 9, 2, 5, 10] k = 三output: 84最佳分割方案为:[1, 15, 7] [9] [2, 5, 10] 数组变成:[15, 15, 15, 9, 10, 10, 10]
题目解析
对于数组 arr,分割后每段数组的长度不得超过 k。
arr = [1, 15, 7, 9, 2, 5, 10]k = 分割结果:[1, 15, 7] [9] [2, 5, 例如,我们从后到前分开 数组 [2,5,10] 之后,需要处理的数组 为 [1, 15, 7, 9]处理逻辑与处理整个数组的逻辑相同
由上而言,每一个问题都是与原问题相似的子问题,因此,可以通过递归来解决。
- 提交参数签名进行设计
- 从后到前分割,完成一次分割后,数组的长度发生了变化。因此,递归参数是 数组的最后一段开始下标
- 如何找到数组开始下标的最后一段,主题给出了子数组的长度不能超过k
- 所以起点为 n - k + 1
- 递归逻辑
- 数组枚举最后一段开始下标 j = n - k + 1 递归起点 i = n - 1
- 由于所有值都将成为这个段子数组的最大值, 一共 i - j + 1 个元素
- 所以有
- 最后一段的数组长度不得超过 k 所以 j 的最小为 max(i-k+1, 0) (j 不能是负数)
- 最后一段数组的元素,加上 dfs(j - 1) 这个子问题的结果,再取最大值,即 dfs(i)
- 公式为
- python
class Solution: def max_sum_after_partitioning(self, arr: List[int], k: int) -> int: @cache # 优化点: 缓存装饰器,避免重复计算 dfs 的结果 def dfs(i: int) -> int: res = mx = 0 for j in range(i, max(i - k, -1), -1): mx = max(mx, arr[j]) res = max(res, dfs(j - 1) + (i - j + 1) * mx) return res return dfs(len(arr) - 1)
- Java
private int[] arr // 优化点:存储递归结果,避免重复计算. private int[] memo; private int k; public int maxSumAfterPartitioning(int[] arr, int k) { this.arr = arr; this.k = k; int n = arr.length; memo = new int[n]; Arrays.fill(memo, -1); return dfs(n - 1); }private int dfs(int i) { if(i < 0) { return 0; } if(memo[i] != -1) { return memo[i]; } int res = 0; for(int j = i,max_num = 0;j > i-k && j >= 0;j--) { max_num = Math.max(max_num, arr[j]); res = Math.max(res, dfs(j - 1) + (i - j + 1) * max_num); } return memo[i] = res; }
- 翻译成递推
public int maxSumAfterPartitioning(int[] arr, int k) { int n = arr.length; int[] dp = new int[n+1]; for(int i = 0;i < n;i++) { for(int j = i,max_num = 0;j > i - k && j >= 0;j--) { max_num = Math.max(max_num, arr[j]); dp[i+1] = Math.max(dp[i+1], dp[i] + (i - j + 1) * max_num); } } return dp[n];}