动态规划🐑

最大子序和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

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

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

解法：动态规划

示例：[a,b,c,d,e]，解答这类题目，少不了遍历，先从遍历方式说起：
通常我们遍历子串或者子序列有三种遍历方式：

• 以某个节点为开头的所有子序列，如，[a]，[a,b]，[a,b,c]…再从以b为开头的子序列开始遍历[b],[b,c]
• 根据子序列的长度为标杆，如先遍历出子序列长度为1的子序列，再遍历出长度为2的等等
• 以子序列的结束节点为基准，先遍历出以某个节点为结束的所有子序列，因为每个节点都可能会是子序列的结束节点，因此要遍历下整个序列，如: 以 b 为结束点的所有子序列: [a , b] [b] 以 c 为结束点的所有子序列: [a, b, c] [b, c] [ c ]。

因为我们通常的惯性思维是以子序列的开头为基准，先遍历出以 a 为开头的所有子序列，再遍历出以 b 为开头的…但是动态规划为了找到不同子序列之间的递推关系，恰恰是以子序列的结束点为基准的

var maxSubArray = function(nums) {
    let ans = nums[0];
    let sum = 0;
    for(let num of nums) {
        if(sum + num > num ){
            sum = sum + num;
        } else {
            sum = num;
        }
        ans = Math.max(ans, sum);
    };
    return ans;
};