33. 最大子序和 (maximum-subarray)

标签

• 动态规划
• 简单

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

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

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

相关知识

动态规划

首先，动态规划和递推有些相似（尤其是线性动规），但是不同于递推的是：

• 递推求出的是数据，所以只是针对数据进行操作；

• 而动态规划求出的是最优状态，所以必然也是针对状态的操作，而状态自然可以出现在最优解中，也可以不出现——这便是决策的特性（布尔性）。

• 可推导性: 其次，由于每个状态均可以由之前的状态演变形成，所以动态规划有可推导性，

• 无后效性: 但同时，动态规划也有无后效性，即每个当前状态会且仅会决策出下一状态，而不直接对未来的所有状态负责，可以浅显的理解为——Future never has to do with past time ,but present does. (现在决定未来，未来与过去无关。)

动态规划的适用情况

1. 最优子结构

如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2. 无后效性

即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

3. 子问题重叠

子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

动态规划的例子

我们所熟知的斐波那契数列的递推式就是动态规划的一种体现

1. 递归法求解

let fibonacci = (n) => {
  if (n == 1 || n == 2) {
    return 1
  };
  return fibonacci(n - 2) + fibonacci(n - 1);
}
console.log(fibonacci(5))

我们会发现上面的程序在超过多少项之后计算速度就会以肉眼可见的速度下降，原因是什么呢，就是因为该程序在计算的过程中遇到了大量的子问题的重叠计算。

2. DP

let fibonacciWithDP = (n) => {
  let f = [], i = 3
  f[1] = 1 
  f[2] = 1
  for (i; i <= n; i++) {
    f[i] = f[i - 1] + f[i - 2]  // 重要递推
  }
  return f
}
console.log(fibonacciWithDP(5))

动态规划解决问题的一般步骤

1. 寻找最优子结构(状态表示)
2. 归纳状态转移方程(状态计算)
3. 边界初始化

接下来我们看下面具体问题

基本思路

状态表示: dp[i] 表示 [0,i] 区间内各个子区间和的最大值

状态转移方程：

• dp[i] = nums[i] + dp[i-1] (dp[i-1] > 0)
• dp[i] = nums[i] (dp[i-1] ≤ 0)

写法实现

var maxSubArray = function(nums) {
    let res = nums[0];
    // 当前最大序列和为 currentMaxSum
    let currentMaxSum = 0;
    nums.map(item => {
      currentMaxSum = Math.max(currentMaxSum + item, item)
      res = Math.max(res, currentMaxSum);
    })
    return res;
};

let nums = [-2,1,-3,4,-1,2,1,-5,4]
console.log(maxSubArray(nums))

为什这段没更新？简单来说，我去生了个小孩，还回家洗了个澡换了身衣服，所以没更新。最近更新肯定会受影响。

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦 搜索我的微信号infinity_9368，可以聊天说地 加我暗号 "天王盖地虎" 下一句的英文，验证消息请发给我 presious tower shock the rever monster，我看到就通过，暗号对不上不加哈，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧

参考

• www.cnblogs.com/wlw-x/p/125…