题目

难度级别：简单

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

示例:

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

进阶:

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

解题思路

法一

通过动态规划，一次遍历数组，若前一项为负数，则当前项不变，若前一项为正数，则当前项与前一项求和，最后输出最大数。

const maxSubArray = function(nums) {
    let max = nums[0]

    for (let i = 1; i < nums.length; i++) {
        if (nums[i - 1] > 0) {
            nums[i] += nums[i - 1]
        }
        max = nums[i] > max ? nums[i] : max
    }

    return max
};

时间复杂度：O(n) 只需遍历一遍
空间复杂度：O1 只需加减这样的常数计算

法二

使用贪心算法，通过变量保存之前和与最大和，遍历数组时，若之前和小于0，则当前项不变。最后输出最大和。

const maxSubArray = function(nums) {
    let lastSum = nums[0]
    let maxSum = lastSum

    for (let i = 1; i < nums.length; i++) {
        if (lastSum < 0) {
            lastSum = nums[i]
        }else{
            lastSum += nums[i] 
        }
        maxSum = lastSum < maxSum ? maxSum : lastSum
    }

    return maxSum
};

时间复杂度：O(n) 只需遍历一遍
空间复杂度：O1 只需加减这样的常数计算

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray