一、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


