「动态规划」「leetcode」53.最大子序和

原题

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

思路

举一个例子，假设一组数字nums如下[-2,1,-3,4,-1,2,1]。

对于前面一个数，如果需要包含第一个数的，最大子数组的和。dp(0) = -2。子数组为[-2]

对于前面两个数，如果需要包含第二个数的，最大子数组的和。要么等于nums[1]，要么等于nums[1] + dp(0), 由于dp(0)是负数，加上它，不如不加，所以dp(1) = nums[1] = 1。子数组为[1]

对于前面三个数，如果需要包含第三个数的，最大子数组的和。要么等于nums[2], 要么等于nums[2] + dp(1), 由于nums[2]自身等于是负数，但是dp(1)是正数，所以dp(3) = nums[2] + dp(1) = nums[2] + 1 = -3 + 1 = -2。子数组为[1, -3]

对于前四个数，如果需要包含第四个数的，最大子数组的和。要么等于nums[3], 要么等于nums[3] + dp(2), 由于dp(2)等于-2, 反而会减小nums[3]的大小，所以dp(4) = nums[3] = 4。子数组为[4]

…………

依次向下类推。我们可以发现。

对于第i个数。第i-1个数是正数，还是负数并不重要，重要的是包含第i-1个数的最大子数组的和是正的还是负的。如果是正的，我们应该拥有它。如果是负的，我们不应拥有它。

如果包含，第i-1个数的最大子数组和，是正数，那么dp(i) = vi + dp(i - 1)。

如果包含，第i-1个数的最大子数组和，是负数，那么dp(i) = vi。

那么我们可以总结出，如下状态转移方程

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {

    if (nums.length === 0) {
        return 0
    }
    
    if (nums.length === 1) {
        return nums[0]
    }
    
    let max_value = Number.MIN_SAFE_INTEGER
    
    for (let i = 0; i < nums.length; i++) {
        let m = nums[i]
        let n = dp[i - 1] === undefined ? 0 : dp[i - 1]
        n = n + m
        dp[i] = Math.max(n, m)
        
        if (dp[i] > max_value) {
            max_value = dp[i]
        }
    }
    
    console.log(dp, max_value)
    
    return max_value
};