博客

一、题目描述

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

二、示例

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

示例二
输入：nums = [1]
输出：1

示例三
输入：nums = [5,4,-1,7,8]
输出：23

三、解题思路

这里我们以数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]为例,因为这个要求是连续的数组。
当数组[-2]，max = -2
当数组为[-2, 1] max = 1  //因为之前的max + current < currrent,所以我们将之前的删除。所以此时数组为[1]
当数组为[1, -3]时 max = -3 //因为 max + current = -2 > current = -3,所以当前数组为[1,-3]
当数组为[1, -3, 4]时，max = 4. //因为max + current = 2 < current = 4,所以当前的数组为[4]
当数组为[4, -1]时， max = 3 //因为 max + current = 3 > current = -1,所以当前数组为[4, -1]
当数组为[4, -1, 2]是，max = 5，//因为max + current = 3 + 2 = 5 > current = 2,所以当前数组为[4, -1, 2]
当数组为[4,-1,2,1]时，max = 6，//因为max +current = 5 + 1 = 6 > current = 1，所以当前数组为[4, -1,2, 1]
当数组为[4,-1,2,1,-5]时，max = 1, //因为max + current = 6- 5 = 1 > current = -5,所以当前数组为[4,-1,2,1,-5].
当数组为[4,-1,2,1,-5,4]时，max = 5,//因为max + current = 1 + 4 = 5 > current = 4,所以当前数组为[4,-1,2, 1, -5, 4]

如上述代码所示，此时最大值为

[4，-1, 2, 1]

，此时我们应该使用一个变量来保存每次最大值。


四、代码展示

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let result = nums[0]
    let max = nums[0]
    let current = nums[0]
    for(let i = 1; i < nums.length; i++) {
        current = nums[i]
        max = Math.max(max + current, current)
        result = Math.max(max, result)
    }
    return result
};

五、结果