力扣 Hot 100 普通数组题解 Python 版

一、53. 最大子数组和

思路 1：前缀和优化

维护最小前缀和，避免双重循环。

class Solution:
    def maxSubArray(self, nums):
        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[i] 表示以 nums[i] 结尾的最大子数组和。状态转移方程为 dp[i] = max(dp[i-1], 0) + 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. 合并区间

思路

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

class :
     () -> [[]]:
        intervals.sort(key= p: p[])
        res = []
         p  intervals:
             res  p[] <= res[-][]:
                res[-][] = (res[-][], p[])
            :
                res.append(p)
         res