建设文明网站包括,网站的详情页面,免费手机网页网站,微信公众平台官网入口#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 暴力法 求解思路 实现代码 运行结果 ⚡ 记忆化搜索 求解思路 实现代码 运行结果 ⚡ 动态规划 求解思路 实现代码 运行结果 共勉 题目链接
410. 分割数组的最大值
⛲ 题目描述
给定一个非负整数数组 nums 和一个整数 m 你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1
输入nums [7,2,5,10,8], m 2 输出18 解释 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18在所有情况中最小。 示例 2
输入nums [1,2,3,4,5], m 2 输出9 示例 3
输入nums [1,4,4], m 3 输出4
提示
1 nums.length 1000 0 nums[i] 106 1 m min(50, nums.length) 求解思路实现代码运行结果 ⚡ 暴力法 求解思路
简单概括题目的意思:我们需要将给定的数组nums划分为k个子数组然后找到每一次可以进行划分方案中的最大值然后将所有可行的方案中的最小值找出来即可。怎么做呢我们就可以枚举每一个开始的位置i通过前缀和快速求解从left到i位置子数组的和然后递归去求后面重复子规模的结果。有了基本的思路接下来我们就来通过代码来实现一下。 实现代码
class Solution {int[] sum;int[] nums;int k;int n;public int splitArray(int[] nums, int k) {this.nnums.length;this.numsnums;this.kk;sumnew int[n1];for(int i1;in;i){sum[i]sum[i-1]nums[i-1];}return process(0,0);}public int process(int left,int cnt){if(cnt1k){return sum[n]-sum[left]; }int minInteger.MAX_VALUE;for(int ileft;inums.length;i){int maxMath.max(sum[i1]-sum[left],process(i1,cnt1));minMath.min(min,max);}return min;}
}运行结果
时间超出了限制但是不要紧张这是我们想要的结果 ⚡ 记忆化搜索 求解思路
因为在递归的过程中会重复的出现一些多次计算的结果我们通过开辟一个数组将结果提前缓存下来算过的直接返回避免重复计算通过空间来去换我们的时间。 实现代码
class Solution {int[] sum;int[] nums;int k;int[][] dp;int n;public int splitArray(int[] nums, int k) {this.nnums.length;this.numsnums;this.kk;sumnew int[n1];dpnew int[n1][k1];for(int i0;in;i) Arrays.fill(dp[i],-1);for(int i1;in;i){sum[i]sum[i-1]nums[i-1];}return process(0,0);}public int process(int left,int cnt){if(cnt1k){return sum[n]-sum[left]; }if(dp[left][cnt]!-1) return dp[left][cnt];int minInteger.MAX_VALUE;for(int ileft;inums.length;i){int maxMath.max(sum[i1]-sum[left],process(i1,cnt1));minMath.min(min,max);}return dp[left][cnt]min;}
}运行结果
通过缓存将重复计算的结果缓存下来通过。 时间情况
空间情况 ⚡ 动态规划 求解思路
有了递归有了记忆化搜索接下来就是动态规划了直接上手。 实现代码
class Solution {int[] sum;int[] nums;int k;int[][] dp;int n;public int splitArray(int[] nums, int k) {this.nnums.length;this.numsnums;this.kk;sumnew int[n1];dpnew int[n1][k1];for(int i1;in;i){sum[i]sum[i-1]nums[i-1];}for(int i 0; i n; i){Arrays.fill(dp[i], Integer.MAX_VALUE);}dp[n][k]0;for(int leftn-1;left0;left--){for(int cntk-1;cnt0;cnt--){int minInteger.MAX_VALUE;for(int ileft;in;i){int maxMath.max(sum[i1]-sum[left],dp[i1][cnt1]);minMath.min(min,max);}dp[left][cnt]min;}}return dp[0][0];}
}运行结果
动态规划搞定大家可以积极的尝试。
时间复杂度
空间复杂度 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
