283. 移动零 (Move Zeroes)
题目描述：给定一个数组nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。
复盘笔记：这题的核心是快慢双指针（同向奔跑）。可以把快指针想象成“探路者”，无脑往前冲去找非零数字；慢指针想象成“收纳盒”，停在前面等待接收。探路者一旦找到非零数字，就直接和收纳盒里的东西互换，然后大家一起往前走一步。这样遍历一次，所有的 0 自然就被“挤”到末尾了。
class Solution: def moveZeroes(self, nums: List[int]) -> None: n = len(nums) left = 0 right = 0 while right < n: if nums[right] != 0: nums[left], nums[right] = nums[right], nums[left] left += 1 right += 153. 最大子数组和 (Maximum Subarray)
题目描述：给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
复盘笔记：主要用到了分治法（线段树的核心思想）。 它的核心思路是把数组不断对半劈开，直到变成单个元素，然后再一层层向上合并（pushUp）。 最烧脑的地方在于，为了能让父区间正确合并，每一个子区间都必须维护四个状态：
iSum：区间的总和。lSum：靠着左边界的最大子段和。rSum：靠着右边界的最大子段和。mSum：整个区间内的最大子段和（也就是我们最终要求的答案）。
在做的时候，合并逻辑（pushUp）一开始很容易想不清楚。比如父区间的mSum，它可能完全在左子区间，也可能完全在右子区间，还可能是跨越了中间边界（左子区间的rSum+ 右子区间的lSum）。必须用max()把这三种情况都考虑进去。
class Status: def __init__(self, lSum: int, rSum: int, mSum: int, iSum: int): self.lSum = lSum # 包含左端点的最大子段和 self.rSum = rSum # 包含右端点的最大子段和 self.mSum = mSum # 该区间内的最大子段和 self.iSum = iSum # 该整个区间的和 class Solution: def pushUp(self, l: Status, r: Status) -> Status: # 整个区间的和 = 左子区间的和 + 右子区间的和 iSum = l.iSum + r.iSum # 包含左端点的最大和 = max(左子区间的 lSum, 左子区间的全部和 + 右子区间的 lSum) lSum = max(l.lSum, l.iSum + r.lSum) # 包含右端点的最大和 = max(右子区间的 rSum, 右子区间的全部和 + 左子区间的 rSum) rSum = max(r.rSum, r.iSum + l.rSum) # 区间内的最大和 = max(左子区间的最大和, 右子区间的最大和, 横跨左右子区间的最大和) # 注意：Python 的 max 函数可以直接接收多个参数 mSum = max(l.mSum, r.mSum, l.rSum + r.lSum) return Status(lSum, rSum, mSum, iSum) def get(self, a: list[int], l: int, r: int) -> Status: # 递归的 base case：区间长度为 1，直接返回该元素的值 if l == r: return Status(a[l], a[l], a[l], a[l]) # 位运算求中间索引，等同于 (l + r) // 2 m = (l + r) >> 1 # 分治：分别求解左右子区间 lSub = self.get(a, l, m) rSub = self.get(a, m + 1, r) # 合并左右子区间的状态 return self.pushUp(lSub, rSub) def maxSubArray(self, nums: list[int]) -> int: # 获取整个数组 [0, len(nums)-1] 的 Status，并提取其中的 mSum（全局最大子段和） return self.get(nums, 0, len(nums) - 1).mSum
