携手创作，共同成长！这是我参与「AdminJS · 8 月更文挑战」的第1天，点击查看活动详情
一小段废话：其实在更文活动下面很少看到有 6 级作者会选择坚持更文了。可能更文活动的主要面向对象是初中级写作的掘友。但自问一句，6 级作者就是写作高手了吗？未必吧。 有 3 点思考：1. AdminJS是一个在成长的技术平台，以前的流量分配也未必精准，有些文章可能发展期意外被推流了，也并不能说明什么。很多作者也是，曾经辉煌过，但后续因为某些原因，也逐渐也在创作视野中消失了。写作很难是一锤定音、一招即中，也不是标准意义上的被动收入，唯有持续才有长久。2. 真的能保证在放弃持续更文的情况下，创作好文吗？不知道别人如何，本瓜更多的是在持续更的过程中才会迸发一些好文的灵感或创作出好文。如果空想、干想好文，结果就是被拖延搁置了。3. 能薅一下羊毛也挺不错的吧？虽然有些东西也没啥用，但是每次拿到证书、更文激励，还是会开心满足。认真做过的都知道是不简单的，所以就做吧，以一颗初心，学徒之心，苟日新、日日新！！
对于前端是否该面试算法的观点都在这篇文章《面试官：工作两年了，这么简单的算法题你都不会？》里面了。其中有一句：
技术题目无罪，不要让不好的面试体验干涉到技术学习上来。
是的，算法题是绝对有它本身价值的！
对算法感到畏惧的 xdm，咱不求一口吃个胖子，先对算法简单题重拳出击，尝试建立自信，训练基础算法思维，不日定能大杀四方、所向披靡。
OK，闲言少叙，上题：
这是一道经典题：# 剑指 Offer 42. 连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
这题的基础算法思维是：动态规划（Dynamic programming，简称DP）
- 老观众都知道之前在讲狄克斯特拉最短路径问题有提过这个，有兴趣去专栏翻一翻。
DP的操作过程，一言以蔽之：大事化小，小事化了。 即将一个大问题转化成几个小问题；求解小问题；推出大问题的解。
解：
1、题目要求的是给出连续最大子数组和是多少，而没有要求给出连续最大子数组是哪一个。明白这一点很重要。
2、其次，题目要求了，时间复杂度要是 O(n) ，所以只能用一次遍历。
3、接着，最关键的是，怎么理解“连续最大”。“连续最大数组的特点是什么？”答案是：
- 连续最大的数组的最后一位肯定是一个正数，要不然还把它纳入进来干嘛？
- 然后，这个正数前面的几个数字之和也要是正数！要不然还要它前面的纳入干嘛？
有了上面的认识，我们用一层 for 循环，用 sum 变量来收集当前遍历的数字前面数字的最大和，如果这个最大和大于0，则加上当前遍历数字，如果这个最大和小于0，则让最大和直接等于正在遍历的数字。最终的结果 res 在上一轮的最大和和这一轮的计算后的最大和中取最大值。
比如数组是 [-2,1,3,-4,5]：res 初始值为 nums[0]，即为 -2；
开始遍历：
[-2]，sum = -2 res = -2
[-2,1] sum 在上一轮为 -2，小于 0 ，此时，最大和等于 1，供下一轮判断使用 ，res = max(-2,1)
[-2,1,3] sum 在上一轮为 1，大于 0，此时最大和等于 1+3=4，res = max(1,4)
[-2,1,3,-4] sum 在上一轮为 4 ，大于0，此时最大和等于 4-4=0，res= max(4,0)
[-2,1,3,-4,5] sum 在上一轮为 0， 等于0，此时最大和等于 0+5=5，res=max(4,5)
所以：
如果
sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字如果
sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字每次比较
sum和res的大小，将最大值置为res，遍历结束返回结果
代码实现：
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let res = nums[0];
let sum = 0;
for(const num of nums) {
sum > 0 ? sum+=num : sum = num
res = Math.max(res, sum);
}
return res;
};
小结：
本题，思路很重要。想明白给的条件的引申解释123点，再跟着示例去走一遍，代码中的 DP 思路就很好理解了~
OK，以上便是本篇分享。点赞关注评论，为好文助力