零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（53）最大子数组和
一 题目形容
二 解法总览（思维导图）
三 全副解法
1 计划1
1)代码：
// 解法1 “本人。贪婪法”。// 思路：// 1）状态初始化 l = nums.length; sum = 0, resMaxVal = Number.NEGATIVE_INFINITY; 。// 2）外围：遍历数组。// 2.1）外围：若 此时 sum < 0，阐明我还不如从0开始 —— 即重置sum为0。// 2.2）sum 加上以后值 num[i] 。// 2.3）依据 sum 状况，更新 resMaxVal 值。// 3）返回后果 resMaxVal 。var maxSubArray = function(nums) { // 1）状态初始化 l = nums.length; sum = 0, resMaxVal = Number.NEGATIVE_INFINITY; 。 const l = nums.length; let sum = 0, resMaxVal = Number.NEGATIVE_INFINITY; // 2）外围：遍历数组。 for (let i = 0; i < l; i++) { const tempVal = nums[i]; // 2.1）外围：若 此时 sum < 0，阐明我还不如从0开始 —— 即重置sum为0。 if (sum < 0) { sum = 0; } // 2.2）sum 加上以后值 num[i] 。 sum += tempVal; // 2.3）依据 sum 状况，更新 resMaxVal 值。 resMaxVal = Math.max(resMaxVal, sum); } // 3）返回后果 resMaxVal 。 return resMaxVal;}2 计划2
1)代码：
// 解法2 “动静规划法”。// 参考：// 1）https://leetcode.cn/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/// 思路：// 状态定义：dp[i] 示意以地位 i 结尾的最大子数组和。// 状态转移：dp[i] = max(nums[i], nums[i] + dp[i - 1])。// 1）状态初始化 l = nums.length; dp = [nums[0]]; 。// 2）外围：状态转移。// 3）dp里的最大值就是答案 —— resMaxVal 。// 4）返回后果 resMaxVal 。var maxSubArray = function(nums) { // 1）状态初始化 l = nums.length; dp = [nums[0]]; 。 const l = nums.length; let dp = [nums[0]]; // 2）外围：状态转移。 for (let i = 1 ; i < l; i++) { const tempVal = nums[i]; dp[i] = Math.max(tempVal, tempVal + dp[i - 1]); } // 3）dp里的最大值就是答案 —— resMaxVal 。 const resMaxVal = Math.max(...dp); // 4）返回后果 resMaxVal 。 return resMaxVal;}3 计划3
1)代码：
// 计划3 “分治法”。// 注：“仿佛工夫、空间复杂度都不是很好~”。// 参考：// 1）https://leetcode.cn/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/// 思路：// 暂略（TODO）。var maxSubArray = function(nums) { const Status = function(l, r, m, i) { this.lSum = l; this.rSum = r; this.mSum = m; this.iSum = i; } const pushUp = (l, r) => { const iSum = l.iSum + r.iSum; const lSum = Math.max(l.lSum, l.iSum + r.lSum); const rSum = Math.max(r.rSum, r.iSum + l.rSum); const mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum); return new Status(lSum, rSum, mSum, iSum); } const getInfo = (a, l, r) => { if (l === r) { return new Status(a[l], a[l], a[l], a[l]); } const m = (l + r) >> 1; const lSub = getInfo(a, l, m); const rSub = getInfo(a, m + 1, r); return pushUp(lSub, rSub); } return getInfo(nums, 0, nums.length - 1).mSum;}四 资源分享 & 更多
1 历史文章 - 总览
2 博主简介
码农三少 ，一个致力于编写 极简、但齐全题解（算法） 的博主。
专一于 一题多解、结构化思维 ，欢送一起刷穿 LeetCode ~