Skip to content

Latest commit

 

History

History
147 lines (111 loc) · 3.63 KB

20200627-53.maximum-subarray.md

File metadata and controls

147 lines (111 loc) · 3.63 KB

#53.maximum-subarray

题目链接：https://leetcode-cn.com/problems/maximum-subarray/

参考链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/

题目

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

示例：

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

进阶:

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

解题

思路[1]动态规划

  • 以当前点为终点的连续子数组的和就等于当前点的值与之前最大和+当前点的值相加的相比较取最大值
  • 动态规划的思路就是找当前点的值与之前点的关系

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  let pre = 0, maxAns = nums[0];
  nums.forEach((x) => {
    pre = Math.max(pre + x, x);
    maxAns = Math.max(maxAns, pre);
  });
  return maxAns;
};

思路[2]贪心

  • 遇到当前数大于0时，这个数与下一个数加和一定比下一个数大，所以加和，将数组按序操作一遍后，就得到了以当前点为终点的连续子数组的和的一个数组，求其中最大值就好。
  • 从头开始加和，遇到加和小于0的时候就舍弃之前的和，从当前数开始从新开始加和，即小于0的部分一定带来的是负收益，舍弃负收益，才能找到最大的。

代码

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

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

思路[3]分治

  • 将数组分为2段，父区间的最大连续子数组这个时候分为三种情况

    • 在左子区间
    • 在右子区间
    • 跨度在中间

  • 在左右子区间的时候都好计算，即求出左右子区间最大的子数组和

  • 在中间的情况比较复杂，因为要处理连续增加的情况

  • 如果左子区间或者右子区间是个连续增加情况，那么父区间的左侧值就等于左子区间的区间与右子区间的左侧边界的和，右侧值也相同

[1,2,3,4] => [1,2] [3,4] => [1][2][3][4] => [1,1,1,1][2,2,2,2][3,3,3,3][4,4,4,4] => [3,3,3,3][7,7,7,7] => [10,10,10,10]


#### 代码

/**

  • @param {number[]} nums
  • @return {number} */ var Status = function(l, r, i, s){ this.l = l; // 跨中心时要和右边界合并的值 this.r = r; // 跨中心时要和左边界合并的值 this.i = i; // 区间和，用于计算l和r this.s = s; // 最大字段和 }

var pushUp = function(lNode, rNode){ let l = Math.max(lNode.l, rNode.l + lNode.i) let r = Math.max(rNode.r, rNode.i + lNode.r) let i = lNode.i + rNode.i; let s = Math.max(lNode.s, rNode.s, lNode.r + rNode.l) return new Status(l, r, i, s) }

var getInfo = function(a, l, r){ if(l === r) return new Status(a[l], a[l], a[l], a[l]); const m = (l + r) >> 1; let lNode = getInfo(a, l, m); let rNode = getInfo(a, m+1, r); return pushUp(lNode, rNode); }

var maxSubArray = function(nums) { return getInfo(nums, 0, nums.length - 1).s; };




### 思考

* 最后的分治较难理解，主要是注意跨区间的问题