53. 最大子数组和

• 题号：53
• 来源：LeetCode
• 难度：中等
• 标签：dp 数组 子数组
• 语言：TypeScript · Python
• 解法：2 个
• 作者：lmliheng
• 最近更新：2026-09-29

TypeScript

TypeScript · O(n) 时间 · O(n) 空间 · 更新于 2026-09-27

dp为以i结尾的最大和，负数则重新开始

/**
 * @difficulty medium
 * @tags dp,数组,子数组
 * @time O(n)
 * @space O(n)
 * @note dp为以i结尾的最大和，负数则重新开始
 * @53. 最大子数组和
 */

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums: number[]) {
    let dp = new Array(nums.length + 1).fill(0)

    nums.forEach((item, index) => {

        if (dp[index] < 0) {
            dp[index + 1] = item
        } else {
            dp[index + 1] = item + dp[index]
        }
    }
    )
    // 避免dp的初始0
    return Math.max(...dp.slice(1))

};

源码：ts/leetcode/53. 最大子数组和.ts

Python

Python · O(n) 时间 · O(n) 空间 · 更新于 2026-09-29

一维 dp：dp[i]=max(dp[i-1]+nums[i], nums[i])，空间可以再压到 O(1)

"""
@lc 53
@title 最大子数组和
@difficulty medium
@tags dp,数组,子数组
@time O(n)
@space O(n)
@note 一维 dp：dp[i]=max(dp[i-1]+nums[i], nums[i])，空间可以再压到 O(1)
"""

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
        return max(dp)

源码：python/leetcode/hot100/13.py

---

在 GitHub 上查看题目所在目录：lmliheng/algorithm