第5周：最大子数组和问题与动态规划入门

一、上周回顾：分治策略

1.1 核心知识点

• 分治策略：将问题分解为规模更小的相同子问题，递归求解后合并结果。
• 典型例题：寻找两个有序数组的中位数
  从中可提炼出以下能力：
  • 算法思维：将问题转化为寻找“分割点”。
  • 边界处理能力：全面考虑各种边界情况。
  • 代码实现能力：写出简洁、正确的代码。
  • 复杂度分析能力：准确评估时间与空间复杂度。

---

二、真题实战：最大子数组和问题

问题描述：给定一个整数数组（含正、负、零），找出具有最大和的连续子数组，并返回其和。

示例 1

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2

输入：nums = [1] 输出：1

示例 3

输入：nums = [5,4,-1,7,8] 输出：23

提示

• $1 <= nums.length <= 105$
• $-104 <= nums[i] <= 104$

2.1 解法一：分治法（Divide and Conquer）

最大子段和-分治法求解

2.1.1 算法思路

将数组分为左半、右半、跨越中点三部分，分别求解，取最大值。
三种情况互斥且完备，覆盖所有可能的连续子数组。

2.1.2 代码实现注意事项

注意点	说明
递归基（Base Case）	当 left == right 时，返回 nums[left]，不可继续分割。
跨越中点的计算	- 左半部分：从 mid 向左遍历，必须包含 nums[mid] - 右半部分：从 mid+1 向右遍历，必须包含 nums[mid+1]
初始化	左右最大和初始值应设为负无穷（或极小值），但第一个元素必须被包含。
累加方式	边遍历边累加，实时更新最大值，避免冗余计算。
返回值比较	每层递归需比较左、右、跨中三者，返回最大值。
数组边界	严格控制 left 和 right，防止越界。

2.1.3 优缺点分析

• ✅ 优点：逻辑清晰，体现“分而治之”思想，适合理解递归。
• ❌ 缺点：时间复杂度为 O(n log n)，不如动态规划高效。
• 💡 本质：在正负数混合序列中，智能“绕过”负贡献，保留正贡献。

---

2.2 解法二：动态规划（Kadane 算法）

最大子段和-动态规划法求解

2.2.1 核心思想

• 定义状态：dp[i] 表示 以第 i 个元素结尾的最大子数组和。
• 状态转移：

  dp[i] = max(nums[i], dp[i-1] + nums[i])
  

• 最终答案：max(dp[0], dp[1], ..., dp[n-1])

2.2.2 代码实现要点

✅ 正确初始化（避免全负数陷阱）

# 错误 ❌
current_sum = max_sum = 0  # 全负数组会返回0，错误！

# 正确 ✅
current_sum = max_sum = nums[0]

✅ 循环从索引1开始

for num in nums[1:]:
    current_sum = max(num, current_sum + num)
    max_sum = max(max_sum, current_sum)

✅ 状态更新顺序

1. 先更新当前子数组和（current_sum）
2. 再更新全局最大值（max_sum）

✅ 负数处理逻辑

• 并非“遇到负数就重置”，而是判断：
  若 current_sum + num < num，说明之前和为负，应重新开始。

2.2.3 空间优化（状态压缩）

• 原始 DP：O(n) 空间（存储整个 dp 数组）
• 优化后：仅用两个变量，空间复杂度 O(1)

2.2.4 边界测试用例

test_cases = [
    [-2,1,-3,4,-1,2,1,-5,4],  # 混合
    [1],                       # 单元素
    [-1,-2,-3],               # 全负
    [5,4,-1,7,8],             # 多正一负
    [0,0,0,0]                 # 全零
]

2.2.5 其他解法视角：前缀和差值法

def maxSubArray_prefix(nums):
    prefix_sum = 0
    min_prefix = 0
    max_sum = nums[0]
    for num in nums:
        prefix_sum += num
        max_sum = max(max_sum, prefix_sum - min_prefix)
        min_prefix = min(min_prefix, prefix_sum)
    return max_sum

思想：最大子数组和 = 最大前缀和 - 最小前缀和（在它之前）

---

三、动态规划系统总结

3.1 动态规划定义

动态规划（Dynamic Programming） 是一种通过分解重叠子问题、存储子解以避免重复计算，从而高效求解最优化问题的算法思想。

本质：记忆化 + 子问题分解

3.2 适用条件（三要素）

条件	说明	本题体现
最优子结构	原问题最优解包含子问题最优解	全局最大和 = 所有 dp[i] 的最大值
重叠子问题	子问题被多次重复计算	dp[i] 依赖 dp[i-1]，存在递推关系
无后效性	当前状态与历史路径无关	dp[i] 仅由 dp[i-1] 和 nums[i] 决定

3.3 核心要素（DP 四步法）

1. 状态定义
   dp[i] = 以 nums[i] 结尾的最大子数组和

2. 状态转移方程
   dp[i] = max(nums[i], dp[i-1] + nums[i])

3. 边界条件
   dp[0] = nums[0]

4. 计算顺序
   自底向上（从左到右迭代）

3.4 解题步骤模板

1. 问题分析：是否满足 DP 三条件？求最大/最小/方案数？
2. 状态定义：明确 dp 含义（如“以 i 结尾”）
3. 转移方程：列出所有决策选项，写出递推式
4. 边界初始化：处理最小规模问题（如 i=0）
5. 实现与优化：迭代实现，考虑空间压缩
6. 结果提取：从 dp 数组或变量中获取答案

3.5 优化技巧

• 空间优化：若状态仅依赖前一项，可用滚动变量（O(1) 空间）
• 状态压缩：用位掩码等技巧减少状态维度（适用于状态数少的问题）
• 斜率优化：针对特定转移形式进一步优化时间（进阶）

3.6 DP 问题分类

类型	典型问题
线性 DP	最大子数组和、最长递增子序列、背包问题
区间 DP	矩阵链乘、石子合并
树形 DP	树上最大独立集、树的直径
状态压缩 DP	旅行商问题（TSP）、铺砖问题

---

四、延伸思考与应用

4.1 实际应用：股票最大利润

prices = [7,1,5,3,6,4]
differences = [prices[i] - prices[i-1] for i in range(1, len(prices))]
max_profit = maxSubArray(differences)  # 最大子数组和 = 最大利润

启示：算法问题常可通过问题转化映射到现实场景。

4.2 相似问题模式

• 最大乘积子数组（需同时维护最大/最小）
• 环形子数组最大和（分情况讨论）
• 最长递增子序列（不同状态定义）

4.3 工程思维培养

• 防御性编程：检查空输入、单元素等异常
• 测试驱动：设计全面测试用例（尤其边界）
• 性能意识：理解 O(n) 已是最优（必须遍历所有元素）

---

五、再来三个真题

使用最小花费爬楼梯

打家劫舍

买不到的数字

六、本周总结

通过一道“简单”题，我们深入掌握了：

• 算法思想：分治 vs 动态规划的对比与选择
• DP 核心：状态定义、转移方程、边界处理
• 优化能力：空间压缩、代码简洁性
• 工程素养：边界处理、测试思维、异常防御
• 迁移能力：识别问题模式，应用于变种与实际场景

学习哲学：“通过简单问题，学习深刻思想”
本题是动态规划的绝佳入门案例，为后续复杂 DP 问题奠定坚实基础。

---

📌 建议：动手实现三种解法（暴力、分治、DP），并对比性能与代码复杂度，加深理解。