第9章｜动态规划
Unit 04 · LeetCode #53 最大子数组和
先问“必须在哪里结束”，
再问“全局最好在哪里”。
本单元不把 Kadane 算法当作一句口诀。你会先枚举所有连续区间，再发现：为了处理下一个元素，不必保存全部历史，只需要保存“以上一位置结尾的最好区间”。动画持续区分局部状态 ending_here 与全局答案 best_so_far。
已恢复上次学习位置阶段、动画、答题、代码槽位与迁移进度均已恢复。
知识桥梁｜Unit 03 → Unit 04
Unit 03：前缀全局最优
dp[i] 直接表示前 i 间房屋的最大金额，因此答案位于最后一个前缀状态。
全局摘要 → 局部可延长摘要
Unit 04：以当前位置结尾
为了判断下一个元素能否接上，状态必须保留一个“可继续延长”的连续区间，而不能只保存前缀全局最大值。
本单元贯穿问题当前保存的值，是“必须以当前位置结尾的最好结果”，还是“截至目前任何位置的最好结果”？
LeetCode #53 原题题面、示例、约束与提交签名
题目要求
给定一个整数数组 nums，找出一个具有最大和的非空连续子数组，返回该子数组的元素和。
from typing import List
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
pass
输入与输出
- 输入：整数数组
nums； - 输出：任意非空连续子数组能够取得的最大和。
示例
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：[4,-1,2,1] 的和最大。
输出：6
解释：[4,-1,2,1] 的和最大。
输入：nums = [1]
输出：1
输出：1
输入：nums = [5,4,-1,7,8]
输出：23
输出：23
约束与目标复杂度
1 ≤ nums.length ≤ 10⁵；-10⁴ ≤ nums[i] ≤ 10⁴；- 主方法：时间
O(n)，额外空间O(1)。
Subarray
连续且非空。不能跳过中间元素，也不能用空区间得到 0。
ending_here
必须以当前元素结尾的最大连续子数组和，是可被下一位置继续延长的局部状态。
best_so_far
处理到当前索引为止，在所有结束位置中出现过的最大值。
Restart / Extend
当前区间只有两种合法来源：从当前元素重新开始，或延长上一位置的结尾区间。
局部状态型 DP
本环节已完成
请先停留观察当前状态，再决定是否进入下一阶段。