力扣题解分享1043.分割数组以得到最大和

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];}