ARTS(05)

作者: 本一和他的朋友们 | 来源:发表于2022-02-15 12:53 被阅读0次

什么是 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

对我有启发的地方：
我对经历下一个热点技术的发展、追求物质自由两点，感触最深。

个人发展的三个方向

在职场上打拼
去经历有意义有价值的事
1. 到技术创新的发源地去经历创新。比如美国硅谷湾区、北京海淀区、上海张江高科
2. 去经历下一个热点技术的发展。从IT，到互联网、再到移动互联网、云计算、大数据，再到未来的AI，VR，loT。。。技术创新的浪潮是一波接一波的，你是想继在那里继续搬砖搬下去，还是要迎浪而上去经历浪潮
追求一种自由的生活
1. 工作自由
  1. 指的是你不会有失业危机感了。你的技能足够到成为各个公司的抢手货的程度（但是此时工作本质上还是出卖自己的时间，而自己时间有限，还是要多思考思考的）
2. 技能自由
  1. 指的是你可以用自己的技能羊活自己，而不需要去公司里工作。比如开发app，比如做开源社区
  2. 你拥有的编程能力，其实是一种创造的能力，也就是创造力，只要你make something people want，你完全可以通过自己的技能来养活自己
3. 物质自由
  1. 指的是财务自由的另一种说法
  2. 如果想物质自由，一定要学会投资，投资不一定是你的钱，时间也是一种财富，年轻更是，你怎么投资你的时间还有你的青春？你要把你的投资投到什么样的事，什么样的人上？

ARTS(05)

一：算法：

二：阅读，英文技术文章

三：技巧

四：分享

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读