53.最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组 （子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 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
提示：
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
解法
1.动态规划
步骤
1，确定状态
2，找到转移公式
3，确定初始条件以及边界条件
4，计算结果。
定义
dp[i]表示数组中前i+1（注意这里的 i 是从 0 开始的）个元素构成的连续子数组的最大和。如果要计算前 i+1 个元素构成的连续子数组的最大和，也就是计算 dp[i]，只需要判断 dp[i-1]是大于 0 还是小于 0。如果 dp[i-1]大于 0，就继续累加，dp[i]=dp[i-1]+num[i]。如果 dp[i-1]小于 0，我们直接把前面的舍弃，也就是说重新开始计算，否则会越加越小的，直接让 dp[i]=num[i]。所以转移公式如下
dp[i] = num[i] + max(dp[i - 1], 0);
- 边界条件判断，当 i 等于 0 的时候，也就是前 1 个元素，他能构成的最大和也就是他自己，所以
dp[0] = num[0];
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
const length = nums.length;
const dp = [];
dp[0] = nums[0];
let max = dp[0];
for (let i = 1; i < length; i++) {
dp[i] = Math.max(dp[i - 1], 0) + nums[i];
max = Math.max(dp[i], max);
}
return max;
};
申请了一个长度为 length 的数组，但在转移公式计算的时候，每次计算当前值的时候只会用到前面的那个值，再往前面就用不到了，这样实际上是造成了空间的浪费。这里不需要一个数组，只需要一个临时变量即可
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
const length = nums.length;
const dp = [];
let cur = nums[0];
let max = cur;
for (let i = 1; i < length; i++) {
cur = Math.max(cur, 0) + nums[i];
max = Math.max(cur, max);
}
return max;
};