网站 文件夹 上传,wordpress如何加载ppt,黄石做网站要多少钱,衡水做网站电话文章目录 动态规划题三个重要步骤#xff08;了解思路#xff09;1、问题2、示例3、解决方法#xff08;1#xff09;方法1——动态规划 总结 动态规划题三个重要步骤#xff08;了解思路#xff09; #xff08;1#xff09;定义数组元素的含义 用一个数组来保存历史数… 文章目录 动态规划题三个重要步骤了解思路1、问题2、示例3、解决方法1方法1——动态规划 总结 动态规划题三个重要步骤了解思路 1定义数组元素的含义 用一个数组来保存历史数组。 2找出数组元素直接的关系式状态转移方程 动态规划的题就是把一个规模比较大的问题分成几个规模比较小的问题然后由小的问题推导出大的问题。 常见情况下如上题中nums[start] 和nums[item] 肯定存在某种关系。我们可以从最后一步、倒数第二步等方面入手分析。 3找出初始值 动态规划类似于数学归纳法我们需要知道初始值才能不断地推下去。如该题的-2开始。 1、问题 给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 子数组 是数组中的一个连续部分。 2、示例 示例 1 输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组 [4,-1,2,1] 的和最大为 6 。 示例 2 输入nums [1] 输出1 示例 3 输入nums [5,4,-1,7,8] 输出23 3、解决方法
1方法1——动态规划 // 说实话第一次用动态规划的方法写上面代码有点懵直接debugger看看 // [-2,1-3]中最大的是1那么就不会加上-2和-3这两个值返回的maxArray就是1 // [-2,1-3,4]中最大的是4而4-31大于1但是比4本身小返回的maxArray就是4而不是4-31 2 // [-2,1-3,4,-1]中最大的是4而4 -1 小于4返回的maxArray就还是4 // [-2,1-3,4,-1,2]中最大的是4而4-12大于4返回的maxArray就是5 // [-2,1-3,4,-1,2,1]中最大的是4而4-121大于5返回的maxArray就是6 // 后面的就都不比当前的值大就直接返回了6这么看是不是清晰了点 let nums [-2,1,-3,4,-1,2,1,-5,4]
var maxSubArray function(nums) {// 1-1: 定义一个用来维护当前遍历数据的值let start 0;// 1-2: 要返回的和最大数组值let maxArray nums[0]nums.forEach(item {// 2将起始值和当前值累加与当前值对比获取最大值给起始值start Math.max(startitem, item)// 3: 将起始值和最大值进行对比maxArray Math.max(start, maxArray)// 4遍历后获取n和n1相加后都是最大的那个值});// 5:返回数据console.log(maxArray, maxArray);
};
maxSubArray(nums);总结 难度中等以前是简单的难度 重点了解动态规划的解题思路。
