---

動態規劃題三個重要步驟（了解思路）

（1）定義數組元素的含義
用一個數組來保存歷史數組。
（2）找出數組元素直接的關系式（狀態轉移方程）
動態規劃的題，就是把一個規模比較大的問題分成幾個規模比較小的問題，然后由小的問題推導出大的問題。
常見情況下，如上題中nums[start] 和nums[item] 肯定存在某種關系。我們可以從最后一步、倒數第二步等方面入手分析。
（3）找出初始值
動態規劃類似于數學歸納法，我們需要知道初始值，才能不斷地推下去。如該題的-2開始。

---

1、問題

給你一個整數數組 nums ，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
子數組 是數組中的一個連續部分。

2、示例

示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子數組 [4,-1,2,1] 的和最大，為 6 。
示例 2：
輸入：nums = [1]
輸出：1
示例 3：
輸入：nums = [5,4,-1,7,8]
輸出：23

3、解決方法

（1）方法1——動態規劃

// 說實話，第一次用動態規劃的方法寫上面代碼有點懵，直接debugger看看
// [-2,1-3]中最大的是1，那么就不會加上-2和-3這兩個值，返回的maxArray就是1
// [-2,1-3,4]中最大的是4，而4-3+1大于1，但是比4本身小，返回的maxArray就是4，而不是4-3+1 =2
// [-2,1-3,4,-1]中最大的是4，而4+ -1 小于4，返回的maxArray就還是4
// [-2,1-3,4,-1,2]中最大的是4，而4-1+2大于4，返回的maxArray就是5
// [-2,1-3,4,-1,2,1]中最大的是4，而4-1+2+1大于5，返回的maxArray就是6
// 后面的就都不比當前的值大，就直接返回了6，這么看是不是清晰了點

let nums =  [-2,1,-3,4,-1,2,1,-5,4]
var maxSubArray = function(nums) {// 1-1: 定義一個用來維護當前遍歷數據的值let start = 0;// 1-2: 要返回的和最大數組值let maxArray = nums[0]nums.forEach(item => {// 2：將起始值和當前值累加與當前值對比獲取最大值給起始值start = Math.max(start+item, item)// 3: 將起始值和最大值進行對比maxArray = Math.max(start, maxArray)// 4：遍歷后獲取n和n+1相加后都是最大的那個值});// 5:返回數據console.log('maxArray', maxArray);
};
maxSubArray(nums);

---

總結

難度：中等（以前是簡單的難度）
重點：了解動態規劃的解題思路。