53.最大子数组和

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    // 动态规划，问题拆分，通过求解前一个子问题的解，对后一个子问题提供信息
    // 例如，示例 1 输入数组是 [-2,1,-3,4,-1,2,1,-5,4] ，我们可以求出以下子问题：
    // 子问题 1：以 −2 结尾的连续子数组的最大和是多少；
    // 子问题 2：以 1 结尾的连续子数组的最大和是多少；
    // 子问题 3：以 −3 结尾的连续子数组的最大和是多少；
    // ......
    var sumArr = []
    sumArr[0] = nums[0] // 以-2结尾的最大和
    var max = nums[0]
    for (var i = 1; i < nums.length; i++) {
        // 求以nums[i]结尾的最大和
        // 如果前一个子问题的最大和大于0，则加上前一个子问题的解就等于当前nums[i]结尾的最大和解
        if (sumArr[i - 1] > 0) {
            sumArr[i] = sumArr[i - 1] + nums[i]
        } else {
            sumArr[i] = nums[i]
        }

        // 最终最大和
        max = Math.max(max, sumArr[i])
    }
    return max
}

// 示例 1：
// 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
// 输出：6
// 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));


// 示例 2：
// 输入：nums = [1]
// 输出：1
console.log(maxSubArray([1]));

// 示例 3：
// 输入：nums = [5,4,-1,7,8]
// 输出：23
console.log(maxSubArray([5, 4, -1, 7, 8]));