力扣 Hot100 普通数组题解 Python 实现

一、53. 最大子数组和

• 思路：前缀和优化。维护最小前缀和，避免双重循环。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        res = float('-inf')
        preSum = 0
        minPreSum = 0
        for n in nums:
            preSum += n
            res = max(res, preSum - minPreSum)
            minPreSum = min(minPreSum, preSum)
        return res

• 思路 2：动态规划 (DP)。定义 dp[i] 表示以 nums[i] 结尾的最大子数组和。

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

二、56. 合并区间

• ：先将区间按起始位置排序。遍历区间，若当前区间与结果集最后一个区间有交集则合并，否则添加新区间。