当前位置: 首页 > 图灵资讯 > 技术篇> 力扣题解分享1043.分割数组以得到最大和

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

来源:图灵教育
时间:2023-04-20 17:01:05

 

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 个元素
  • 所以有力扣题解分享1043.分割数组以得到最大和_子数组
  • 最后一段的数组长度不得超过 k 所以 j 的最小为 max(i-k+1, 0) (j 不能是负数)
  • 最后一段数组的元素,加上 dfs(j - 1) 这个子问题的结果,再取最大值,即 dfs(i)
  • 公式为

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

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