最大子序和

[Cosen95]

leetcode: https://leetcode-cn.com/problems/maximum-subarray/

[Cosen95]

本道题目采用动态规划来解决。先给出dp方程：

dp[i] = max(dp[i - 1] + nums[i], nums[i])

我们这里需要两个变量，sum代表累计到当前位置i的最大和，temp代表全局最大子序列和，也就是最终要返回的结果。大致思路就是：

• 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
• 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
• 每次比较 sum 和 temp的大小，将最大值置为temp，遍历结束返回结果

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let temp = nums[0];
    let sum = 0;
    for (const num of nums) {
        if (sum > 0) {
            sum += num
        } else {
            sum = num;
        }
        temp = Math.max(temp, sum)
    }
    return temp;

};