53. 最大子数组和

题目链接：https://leetcode.cn/problems/maximum-subarray/

代码

/**
 * 53. 最大子数组和
 * https://leetcode.cn/problems/maximum-subarray/
 */

function maxSubArray(nums: number[]): number {
    let sum = 0;
    let max = Number.MIN_SAFE_INTEGER; // 初始化为最小数
    for(let i = 0; i < nums.length; i++){
        sum += nums[i];
        if(sum > max){ // 更新最大值
            max = sum;
        }
        if(sum <= 0){ // 当前子数组和为负，对求最大子数组没有好处
            sum = 0; // 重新开始累加
        }
    }
    return max;
}

const nums = [-2,1,-3,4,-1,2,1,-5,4]
console.log(maxSubArray(nums))

思路

使用动态规划 / 前缀和贪心的经典做法：用 sum 记录当前子数组和，max 记录历史最大子数组和。

• 每次把当前元素加到 sum 上；
• 若 sum 比 max 大，则更新 max；
• 如果 sum 小于等于 0，说明这段前缀对后续求最大和没有贡献，直接将 sum 置 0，从下一个位置重新开始。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。