ARTS(05)
什么是 ARTS？
- 算法(Algorithm): 每周至少一道 LeetCode 算法题，加强编程训练和算法学习
- 阅读(Review)： 阅读并点评至少一篇英文技术文章，提高英文水平
- 技巧 (Tip)：学习至少一个技术技巧，总结、归纳日常工作中遇到的知识点
- 分享(Share)：分析一篇有观点和思考的技术文章，建立影响力，输出价值观
时间周期
2022 年 2 月 7 日至 2 月 13日
一：算法：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
前置知识
- 滑动窗口
- 动态规划
思路
从时间复杂度角度可以分析不同的解题思路
解法1:暴力解
一般情况下，先从暴力解分析，然后再进行一步步的优化。
原始暴力解：
求子序列和，那么我们要知道子序列的首尾位置，然后计算首尾之间的序列和。用两个for循环可以枚举所有子序列的首尾位置。然后用一个for循环求解序列和。时间复杂度为O(n3)/
解法2:前缀和+暴力解
在暴力解的基础上，用前缀和 我们可以优化到暴力解O(n2)，这里以空间换时间。可以使用原数组表示prefixSum节省空间。
求序列和可以用前缀和来优化，给定子序列的首尾位置（l, r）。那么序列和subarraySum = prefixSum[r] - prefixSum[l - 1];用一个全局变量maxSum， 比较每次求解的子序列和，maxSum = max(maxSum, subarraySum);
如果用改元数组表示前缀和数组，空间复杂度降为O(1)
解法3:优化前缀和 -form
我们定义函数S(i),它的功能是计算以0（包括0）开始加到I（包括i）的值。
那么s(j) - s(i)就等于从i开始到j的值
实际上我们只需要便利一次计算出所有的S(i),其中i = 0, 1,2,…. n - 1。然后我们再减去之前的S(k),其中k = 0,1,2,…..i - 1，中的最小值即可。因此我们需要用一个变量来为会这个最小值，还需要一个变量来维护最大值。
解法四- 分治法
我们把数组nums以中间位置(m)分为左右两部分，那么left = nums[0]…nums[m - 1] 和right = nums[m + 1] … nums[n-1]
最大子序列和的位置有以下三种情况：
- 考虑中间元素nums[m],跨越左右两部分，这里从中间元素开始，往左求出后缀最大，往右求出前缀最大，保持连续性
- 不考虑中间元素，最大子序列和出现在左半部分，递归求解左边部分最大子序列和
- 不考虑中间元素，最大子序列和出现在右半部分，递归求解右边部分最大子序列和
分别求出三种情况下最大子序列和，三者中最大值即为最大子序列和。
解法五-动态规划
动态规划的难点在于找到状态转移方程。
dp[i] - 表示当前位置i的最大子序列和
状态转移方程为 dp[i] = max(dp[i - 1] + nums[i] , nums[i])
初始化: dp[0] = nums[0]
从状态转移方程，我们只关注一个状态的值，所以不需要开一个数组记录位置所有子序列和，只需要两个变量，
currMaxSum - 累计最大和到当前位置i
maxSum - 全局最大子序列和
关键点分析
- 暴力解，列觉所有组合子序列首尾位置的组合，求解最大的子序列和，优化可以预先处理，得到前缀和
- 分治法，每次从中间位置把数组分为左中右三部分，分别求出左右中最大和。对左右分别深度递归，三者中最大值即为当前最大子序列和。
- 动态规划，找到状态转移方程，求到当前位置最大和。
代码
JavaScript 实现及其拓展资料
/**
* @param {number[]} nums
* @return {number}
*/
// 解法二：前缀和+暴力,执行用时：56 ms
function maxSubArray (nums) {
let length = nums.length;
let max = -Number.MAX_VALUE;
let sum = 0;
for (let i = 0; i < length; i++) {
sum = 0;
for (let j = i; j < length; j++) {
sum += nums[j];
if (sum > max) {
max = sum;
}
}
}
return max;
};
// 解法三：优化前缀和, 执行用时：60 ms
function maxSubArray (nums) {
let length = nums.length;
let max = nums[0];
let min = 0;
let sum = 0;
for (let i = 0; i < length; i++) {
sum += nums[i];
if ((sum - min) > max) {
max = sum - min;
} else if (sum < min) {
min = sum;
}
}
return max;
}
// 解法四：分治法,执行用时：60 ms
function maxSubArray (list) {
return helper(list, 0, list.length - 1)
}
function helper (list, m, n) {
if (m === n) {
return list[m];
}
let sum = 0;
let lMax = -Number.MAX_VALUE;
let rMax = -Number.MAX_VALUE;
let mid = ((n - m) >> 1) + m;
let l = helper(list, m, mid);
let r = helper(list, mid + 1, n);
for (let i = mid; i >= m; i--) {
sum += list[i];
if (sum > lMax) {
lMax = sum;
}
}
sum = 0;
for (let i = mid + 1; i <= n; i++) {
sum += list[i];
if (sum > rMax) {
rMax = sum;
}
}
return Math.max(l, r, lMax + rMax);
}
// 解法五：动态规划,执行用时：76 ms
function maxSubArray (nums) {
let length = nums.length;
let max = nums[0];
for (let i = 1; i < length; i++) {
nums[i] = Math.max(0, nums[i - 1]) + nums[i];
if (nums[i] > max) {
max = nums[i]
}
}
return max;
}
Java 实现及其拓展资料
// 解法二：前缀和 + 暴力
class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
int maxSum = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < len; i++) {
sum = 0;
for (int j = i; j < len; j++) {
sum += nums[j];
maxSum = Math.max(maxSum, sum);
}
}
return maxSum;
}
}
// 解法三：优化前缀和
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int sum = 0;
int minSum = 0;
for (int num: nums) {
sum += num;
maxSum = Math.max(maxSum, sum - minSum);
minSum = Math.min(minSum, sum);
}
return maxSum;
}
}
// 解法四：分治法
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
return helper(nums, 0, nums.length - 1);
}
private int helper(int[] nums, int l, int r) {
if (l > r) {
return Integer.MIN_VALUE;
}
int mid = (l + r) >> 1;
int left = helper(nums, l, mid - 1);
int right = helper(nums, mid + 1, r);
int leftMaxSum = 0;
int sum = 0;
for (int i = mid - 1; i >= l; i--) {
sum += nums[i];
leftMaxSum = Math.max(leftMaxSum, sum);
}
int rightMaxSum = 0;
sum = 0;
for (int i = mid + 1; i <= r; i++) {
sum += nums[i];
rightMaxSum = Math.max(rightMaxSum, sum);
}
return Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left,right));
}
}
// 解法五：动态规划
class Solution {
public int maxSubArray(int[] nums) {
int currMaxSum = nums[0];
int maxSum = nums[0];
for (int i = 0; i < nums.length; i++) {
currMaxSum = Math.max(currMaxSum + nums[i], nums[i]);
maxSum = Math.max(maxSum, currMaxSum);
}
return maxSum;
}
}
二：阅读，英文技术文章
Teach Yourself Programming in Ten Years
三：技巧
你不知道的 Chrome 调试技巧
作为前端，chrome算是打交道最多的开发环境了，这个小册子可以作用入门的介绍，想看更详细的，可以看下google官网的开发者工具文档：https://developer.chrome.com/docs/devtools/overview/
四：分享
https://coolshell.cn/articles/17583.html?from=singlemessage&isappinstalled=0
对我有启发的地方：
我对经历下一个热点技术的发展、追求物质自由两点，感触最深。
个人发展的三个方向
- 在职场上打拼
- 去经历有意义有价值的事
- 到技术创新的发源地去经历创新。比如美国硅谷湾区、北京海淀区、上海张江高科
- 去经历下一个热点技术的发展。从IT，到互联网、再到移动互联网、云计算、大数据，再到未来的AI，VR，loT。。。技术创新的浪潮是一波接一波的，你是想继在那里继续搬砖搬下去，还是要迎浪而上去经历浪潮
- 追求一种自由的生活
- 工作自由
- 指的是你不会有失业危机感了。你的技能足够到成为各个公司的抢手货的程度（但是此时工作本质上还是出卖自己的时间，而自己时间有限，还是要多思考思考的）
- 技能自由
- 指的是你可以用自己的技能羊活自己，而不需要去公司里工作。比如开发app，比如做开源社区
- 你拥有的编程能力，其实是一种创造的能力，也就是创造力，只要你make something people want，你完全可以通过自己的技能来养活自己
- 物质自由
- 指的是财务自由的另一种说法
- 如果想物质自由，一定要学会投资，投资不一定是你的钱，时间也是一种财富，年轻更是，你怎么投资你的时间还有你的青春？你要把你的投资投到什么样的事，什么样的人上？
- 工作自由
