| 🚀 算法题 🚀 |
🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯
| 🚀 算法题 🚀 |
🍔 目录
🚩 题目链接
- 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
🌟 线性dp&求解思路&实现代码&运行结果
⚡ 暴力递归
🥦 求解思路
- 首先根据题目的意思我们知道，题目让我们去求将数组划分成多个长度不超过k的子数组，每一个子数组的值更新为当前子数组中最大的值，最后求得所有划分方案中所有子数组最大的和并返回。
- 那么这个题我们该怎么想呢？因为可以划分的长度最大是k，所以我们可以枚举所有k的选择；
- 那么什么时候去求每个子数组贡献的结果呢？我们可以在遍历的时候，记录当前选择长度内的最大值，然后在调用递归的时候通过之前子数组中的最大值*个数累加到最终的结果中；
- 有了基本的思路，接下来我们就来一起实现代码吧。
🥦 实现代码
java">class Solution {
public int maxSumAfterPartitioning(int[] arr, int k) {
return process(0,arr,k);
}
public int process(int index,int[] arr,int k){
if(index>=arr.length) return 0;
int max=0,num=0;
for(int i=index;i<Math.min(index+k,arr.length);i++){
num=Math.max(num,arr[i]);
max=Math.max(max,process(i+1,arr,k)+num*(i-index+1));
}
return max;
}
}
🥦 运行结果
时间超限了，不要紧哦，我还有锦囊妙计！
⚡ 记忆化搜索
🥦 求解思路
🥦 实现代码
java">class Solution {
int[] dp;
public int maxSumAfterPartitioning(int[] arr, int k) {
dp=new int[arr.length];
Arrays.fill(dp,-1);
return process(0,arr,k);
}
public int process(int index,int[] arr,int k){
if(index>=arr.length) return 0;
if(dp[index]!=-1) return dp[index];
int max=0,num=0;
for(int i=index;i<Math.min(index+k,arr.length);i++){
num=Math.max(num,arr[i]);
max=Math.max(max,process(i+1,arr,k)+num*(i-index+1));
}
return dp[index]=max;
}
}
🥦 运行结果
⚡ 动态规划
🥦 求解思路
🥦 实现代码
java">class Solution {
int[] dp;
public int maxSumAfterPartitioning(int[] arr, int k) {
int n=arr.length;
dp=new int[n+1];
for(int index=n-1;index>=0;index--){
int max=0,num=0;
for(int i=index;i<Math.min(index+k,n);i++){
num=Math.max(num,arr[i]);
max=Math.max(max,dp[i+1]+num*(i-index+1));
}
dp[index]=max;
}
return dp[0];
}
}
🥦 运行结果
🌟 区间dp&求解思路&实现代码&运行结果
⚡ 暴力递归
🥦 求解思路
- 为什么会想到这种递归思路呢？因为题目要我们从开始位置到结束位置进行切割子数组，每个子数组的长度最多可能达到k，此时我们从0位置开始，可以选择的下一个位置小于k即可（[0_k-1]都是可以的），如果说此时我们选择了[0_k-2]进行切割，那么后续的问题就拆解成了[k-1_n-1]的规模，那么整个问题的求解是相同的，并且大规模可以拆解为小规模，此时我们通过递归来做就可以，后续直接改成动态规划。
- 有了具体的实现思路，接下来我们就来一起看一下代码的实现。
🥦 实现代码
java">class Solution {
public int maxSumAfterPartitioning(int[] arr, int k) {
return process(0,arr,k,arr.length-1);
}
public int process(int left,int[] arr,int k,int right){
if(left>right) return 0;
if(right-left<k){
int num=0;
for(int i=left;i<=right;i++) num=Math.max(num,arr[i]);
return num*(right-left+1);
}
int max=0;
for(int i=left;i<left+k;i++){
max=Math.max(max,process(left,arr,k,i)+process(i+1,arr,k,right));
}
return max;
}
}
🥦 运行结果
⚡ 记忆化搜索
🥦 求解思路
🥦 实现代码
java">class Solution {
int[][] dp;
public int maxSumAfterPartitioning(int[] arr, int k) {
int n=arr.length;
dp=new int[n][n];
for(int i=0;i<n;i++) Arrays.fill(dp[i],-1);
return process(0,arr,k,arr.length-1);
}
public int process(int left,int[] arr,int k,int right){
if(left>right) return 0;
if(right-left<k){
int num=0;
for(int i=left;i<=right;i++) num=Math.max(num,arr[i]);
return num*(right-left+1);
}
if(dp[left][right]!=-1) return dp[left][right];
int max=0;
for(int i=left;i<left+k;i++){
max=Math.max(max,process(left,arr,k,i)+process(i+1,arr,k,right));
}
return dp[left][right]=max;
}
}
🥦 运行结果
⚡ 动态规划
🥦 求解思路
🥦 实现代码
java">class Solution {
int[][] dp;
public int maxSumAfterPartitioning(int[] arr, int k) {
int n=arr.length;
dp=new int[n][n];
for(int i=0;i<n;i++) Arrays.fill(dp[i],-1);
for(int left=0;left<n;left++){
for(int right=0;right<n;right++){
if(right-left<k){
int num=0;
for(int i=left;i<=right;i++) num=Math.max(num,arr[i]);
dp[left][right]=num*(right-left+1);
}
}
}
for(int left=n-k-1;left>=0;left--){
for(int right=left+k-1;right<n;right++){
int max=0;
for(int i=left;i<left+k;i++){
max=Math.max(max,dp[left][i]+dp[i+1][right]);
}
dp[left][right]=max;
}
}
return dp[0][n-1];
}
}
🥦 运行结果
💬 共勉
| 最后，我想和大家分享一句一直激励我的座右铭，希望可以与大家共勉！ |
