本文首发于 语雀文档

题目

https://leetcode-cn.com/problems/maximum-subarray/

流程图、调试代码

https://github.com/blueju/leetcode/

第 1 次尝试

一如往常，写不出来，但还是有些小思路的。

1. 看到求最大，想到了《无重复的最长子串》，需要有一个变量将每次求得的和记录起来，并再每次循环中进行进行 max 比较赋值。
2. 第一时间就是想到类似滑动窗口的解法，《无重复的最长子串》中发现重复字符串就会 break，那我们这的 break 的条件是什么呢？（因为不 break 后面的字符串就不再是无重复的了）

看题目名字，应该很快能反应过来，我们 break 的条件是：此次计算的和不再更大时（是不是最大我们不知道，但是如果叠加数任一一个小于零，那和不用说肯定更小）

第 2 次尝试（通过测试用例）

流程图

这次该用 PPT 的形式呈现

最大子序和.pptx

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    let maxSum
    let prevSum
    for (let i = 0; i < nums.length; i++) {
        const length = nums.length
        if (length === 0) {
            return nums[0]
        }
        if (i === 0) {
            maxSum = nums[i]
            prevSum = nums[i]
            currSum = nums[i]
            continue
        }
        if (prevSum < 0) {
            currSum = nums[i]
            maxSum = Math.max(maxSum, currSum)
            prevSum = currSum
        } else {
            currSum = prevSum + nums[i]
            maxSum = Math.max(maxSum, currSum)
            prevSum = currSum
        }
    }
    return maxSum
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    const length = nums.length
    if (length === 1) return nums[0]
    let maxPrevSum
    let maxSum
    for (let i = 0; i < length; i++) {
        if (i === 0) {
            maxPrevSum = nums[i]
            maxSum=nums[i]
            continue
        }
        const currSum = maxPrevSum + nums[i]
        if (currSum < nums[i]) {
            maxPrevSum = nums[i]
            maxSum = Math.max(nums[i], maxSum)
        } else {
            maxPrevSum = currSum
            maxSum = Math.max(currSum, maxSum)
        }
    }
    return maxSum
};