[ 力扣53 ] 最大子序和 | 刷题打卡

题目名称：最大子序和

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

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

解法

一、暴力解垫底

• 外层循环左边界，内层循环右边界所有值，计算最大和,O(n2)复杂度

/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
  if (nums.length <= 1) return nums[0] ? nums[0] : 0
  let max = -Infinity
  for (let i = 0; i < nums.length; i++) {
    let sum = nums[i]
    max = Math.max(max, sum)
    for (let j = i + 1; j < nums.length; j++) {
      sum += nums[j]
      max = Math.max(max, sum)
    }
  }
  return max
};

二、负值舍弃法

• 发现规律，到第 i 个数的时候
  • 如果之前结果+当前值<之前结果，说明当前为负值，就继续扩充区间观察
  • 如果之前结果+当前值>之前结果，说明当前为正直，则扩充区间继续观察
  • 如果之前结果+当前值<当前值，说明之前结果为负值，则果断舍弃之前结果，以当前值为区间起点向后计算

/**
* @param {number[]} nums
* @return {number}
* * [-2,1,-3,4,-1,2,1,-5,4]
*/
var maxSubArray1 = function (nums) {
  let pre = 0, maxAns = nums[0];
  nums.forEach((x) => {
    pre = Math.max(pre + x, x); // * pre 存储的是当前这次最好结果（把当前和之前都带上/只带当前）
    maxAns = Math.max(maxAns, pre);
  });
  return maxAns;
};

• 以上代码带来的疑问：如果区间重置了，但是之前出现过最大结果怎么办？
  • 之前最大结果已经被maxAns记录过了
• 如图所示

三、负值舍弃法升级版：一次循环数组原地记录

• 如果前一个数值为负，我还不如从当下开始计数呢
• 只有前一个数值为正（无论该值是之前累加的还是自身就为正），那就把它算上一起计数
• 最后返回的nums数组中的每一项都是之前项中能够累加的最好情况了，取最大值即可

var maxSubArray2 = function(nums) {
  const n = nums.length;
  for (let i = 1; i < n; i++) {
    if (nums[i-1] > 0) {
      nums[i] += nums[i-1]
    }
  }
  return Math.max(nums)
}

测试用例

// 测试用例
let test = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
let test1 = [-2, 1]

console.time('执行用时');
console.log(maxSubArray(test));
console.log(maxSubArray(test1));
console.log(maxSubArray1(test));
console.log(maxSubArray1(test1));
console.log(maxSubArray2(test));
console.log(maxSubArray2(test1));
console.timeEnd('执行用时');

总结

• 一个对象的Object.entries返回这个对象键值对的数组

• 数组的sort方法如果参数不传，则使用原地算法对数组的元素进行排序，并返回数组。默认排序顺序是在将元素转换为字符串，然后比较它们的UTF-16代码单元值序列时构建的。
  • 字符串情况

• 数字情况

• 结论：通常情况下字符串可以不传参数，但数字数组如果涉及到比较大小必须传入compareFunction才能获得争取的排序结果

说明

1. 本题解已同步GitHub地址，可以复制代码进行调试。
2. 总结出了一套亲测有效的前端无痛刷题项目，有助于算法小白平稳入门，详见leetcode-js-roadmap，希望对从零开始刷题的前端小伙伴们带来帮助~

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情