053 - 最大子序和(maximum-subarray)

Create by jsliang on 2019-06-10 15:15:45
Recently revised in 2019-06-10 17:46:24

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
3.1 解法 - 动态规划

二 前言

返回目录

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 讲解下使用 JavaScript 的解题思路。

3.1 解法 - 动态规划

返回目录

  • 解题代码
var maxSubArray = function(nums) {
  let result = nums[0]; // 最终结果值
  for (let i = 0; i < nums.length; i++) {
    let accumulativeValue = nums[i]; // 本次累加值
    let highest = nums[i]; // 本次最高值
    for (let j = i; j + 1 < nums.length; j++) {
      accumulativeValue = accumulativeValue + nums[j + 1];
      if (accumulativeValue > highest) {
        highest = accumulativeValue;
      }
    }
    if (highest > result) {
      result = highest;
    }
  }
  return result;
};
  • 执行测试

  • nums[1, -2, 2, 3, -1]

  • return
5
  • LeetCode Submit
✔ Accepted
  ✔ 202/202 cases passed (292 ms)
  ✔ Your runtime beats 7.93 % of javascript submissions
  ✔ Your memory usage beats 97.97 % of javascript submissions (34.5 MB)
  • 解题思路

讲道理说,这种解法属于动态规划。

所谓动态规划,就是利用逐步求解,以连续数组结束位置为每一步的解,在这里解法中,resultaccumulativeValuehighest 就是记录的三个值,accumulativeValue 会记录每一步的累积值,然后和 highest 比较,获得本次最高值,最后再将本次最高值 highest 和历史最高值(结果值)result 比较,获得最终结果。

当然,jsliang 解题的时候实际上不会想这么多,无非就是用正常的思路来破解。

  • 进一步思考

其实我一开始(上面解法)的思路还是复杂了,顶多算 暴力破解,所以可以做很大的优化,小伙伴们可以想想,再看看下面的优化。

var maxSubArray = function(nums) {
  let max = nums[0]; // 最高值
  let val = 0; // 累加值
  for (let i = 0; i < nums.length; i++) {
    val = val + nums[i];
    max = val > max ? val : max;
    val = 0 > val ? 0 : val;
  }
  return max;
};
✔ Accepted
  ✔ 202/202 cases passed (72 ms)
  ✔ Your runtime beats 98.5 % of javascript submissions
  ✔ Your memory usage beats 85.94 % of javascript submissions (34.8 MB)

是不是觉得这样子更简练了:

  1. max 为最高值,val 为累加值
  2. 每次累加则判断 valmax 的大小,然后取最大的(相当于 Math.max(val, max))。
  3. 如果 val 小于 0,则重置累加器。为什么呢?就好比 [-1, -3, -2],它每次累加,是不是一定会小于 0?这样我们取每个值比较就行了。再比如当 [-1, 3, 2] 的时候,-1 + 3 是不是一定会小于 3?所以负数是个拖累数,当累加值小于 0 的时候,我们就需要清空计数器了。

不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-06-14 21:45:48

results matching ""

    No results matching ""