https://leetcode-cn.com/problems/maximum-subarray/
点击查看【bilibili】

题目

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

示例

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

解答

动态规划

1. 对于每一个点，都要进行一个抉择：
   • 继续延续之前的数组
   • 用当前值新开一个数组
2. 比较这两个数组和的值，保留最大值

根据上面的算法，以下情况就不需要考虑了

答案

var maxSubArray = function(nums) {
    const memo = []; //保存延续的数组还是新的数组
    memo[0] = nums[0]; // 如果只有一个值，nums[0]就是最大值
    // 从1开始遍历
    for(let i=1; i<nums.length; i++) {
        // 比较延续数组和新开数组的最大值，
        memo[i] = Math.max(nums[i]+memo[i-1], nums[i]) 
    }
    let max = nums[0]
    // 查找最大值
    for(let i=1;i<memo.length;i++) {
        max = Math.max(max,memo[i])
    }
    return max
};

优化方法

var maxSubArray = function(nums) {
    const memo = []; //保存延续的数组还是新的数组
    memo[0] = nums[0]; // 如果只有一个值，nums[0]就是最大值
    let max = nums[0]
    // 从1开始遍历
    for(let i=1; i<nums.length; i++) {
        // 比较延续数组和新开数组的最大值，
        memo[i] = Math.max(nums[i]+memo[i-1], nums[i]) 
        // 找到最大值
        max = Math.max(max,memo[i])
    }
    return max
};