LeetCode刷题实战：用Python搞定最长递增子序列和最大子数组和（附完整代码）
LeetCode刷题实战：Python动态规划解决最长递增子序列与最大子数组和
1. 动态规划基础与问题识别
动态规划（Dynamic Programming）是算法面试中的高频考点，尤其适合解决具有重叠子问题和最优子结构特性的问题。在LeetCode中，线性动态规划问题占据了相当大的比重，其中最长递增子序列（LIS）和最大子数组和（Maximum Subarray）是两类经典问题。
识别动态规划问题的关键特征：
- 最优子结构：问题的最优解包含子问题的最优解
- 重叠子问题：递归算法会重复计算相同的子问题
- 状态转移：当前状态可以由之前的状态推导出来
对于线性DP问题，我们通常使用一维或二维数组来存储中间状态，其中：
dp[i]表示以第i个元素结尾的子问题的解dp[i][j]表示涉及两个序列时，第一个序列前i个元素和第二个序列前j个元素的解
提示：在面试中，90%的动态规划问题都可以用一维或二维DP数组解决，关键在于正确定义状态。
2. 最长递增子序列（LIS）问题详解
2.1 问题描述与状态定义
LeetCode 300题要求找到数组中最长的严格递增子序列长度。子序列不要求连续，但必须保持原始顺序。
例如：
输入：[10,9,2,5,3,7,101,18] 输出：4 # 最长递增子序列是[2,3,7,101]状态定义：
dp[i]：以nums[i]结尾的最长递增子序列长度
2.2 状态转移方程与实现
对于每个元素nums[i]，我们需要检查所有之前的元素nums[j]（j < i）：
if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1)完整Python实现：
def lengthOfLIS(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)复杂度分析：
- 时间复杂度：O(n²) - 双重循环
- 空间复杂度：O(n) - 一维DP数组
2.3 优化策略：二分查找法
对于大规模数据（n>10⁴），O(n²)的解法会超时。我们可以使用贪心+二分查找将复杂度降至O(nlogn)：
def lengthOfLIS(nums): tails = [] for num in nums: left, right = 0, len(tails) while left < right: mid = (left + right) // 2 if tails[mid] < num: left = mid + 1 else: right = mid if left == len(tails): tails.append(num) else: tails[left] = num return len(tails)这种方法维护一个tails数组，其中tails[i]表示长度为i+1的所有递增子序列的最小末尾元素。
3. 最大子数组和问题解析
3.1 问题描述与状态定义
LeetCode 53题要求找到一个具有最大和的连续子数组（子数组最少包含一个元素）。
例如：
输入：[-2,1,-3,4,-1,2,1,-5,4] 输出：6 # 子数组[4,-1,2,1]的和最大状态定义：
dp[i]：以nums[i]结尾的最大子数组和
3.2 状态转移与实现
关键观察：当前元素要么加入前面的子数组，要么自己另起一个新子数组：
dp[i] = max(nums[i], dp[i-1] + nums[i])Python实现：
def maxSubArray(nums): if not nums: return 0 dp = [0] * len(nums) dp[0] = nums[0] for i in range(1, len(nums)): dp[i] = max(nums[i], dp[i-1] + nums[i]) return max(dp)复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
3.3 空间优化：滚动数组
由于dp[i]只依赖于dp[i-1]，我们可以用单个变量代替DP数组：
def maxSubArray(nums): if not nums: return 0 max_sum = current_sum = nums[0] for num in nums[1:]: current_sum = max(num, current_sum + num) max_sum = max(max_sum, current_sum) return max_sum优化后的空间复杂度为O(1)，这是面试官最希望看到的解法。
4. 两种DP问题的对比与实践技巧
4.1 关键差异对比
| 特性 | 最长递增子序列 (LIS) | 最大子数组和 |
|---|---|---|
| 子序列/子数组 | 不要求连续 | 必须连续 |
| 典型状态定义 | dp[i]以nums[i]结尾的LIS | dp[i]以nums[i]结尾的最大和 |
| 时间复杂度 | O(n²)或O(nlogn) | O(n) |
| 空间复杂度 | O(n) | O(1)优化后 |
| 转移方程特点 | 需要遍历之前所有元素 | 只需考虑前一个状态 |
4.2 刷题实战建议
模板化思考：对于DP问题，先明确：
- 状态定义
- 初始条件
- 状态转移方程
- 最终结果如何从DP数组中提取
常见错误：
- 混淆子序列和子数组的概念
- 初始化不正确（特别是边界条件）
- 没有进行空间优化（面试加分项）
测试用例设计：
- 空数组
- 单元素数组
- 全正/全负数组
- 有重复元素的数组
# LIS测试用例示例 test_cases = [ ([], 0), ([1], 1), ([1,3,2,4], 3), ([10,9,2,5,3,7,101,18], 4) ] # 最大子数组和测试用例 test_cases = [ ([], 0), ([-1], -1), ([-2,1,-3,4,-1,2,1,-5,4], 6), ([5,4,-1,7,8], 23) ]4.3 进阶挑战
掌握了这两个基础问题后，可以尝试以下变种：
LIS变种：
- 输出具体的LIS而不仅是长度
- 二维LIS问题（如LeetCode 354. 俄罗斯套娃信封问题）
最大子数组和变种：
- 环形数组的最大子数组和（LeetCode 918）
- 乘积最大子数组（LeetCode 152）
注意：在解决变种问题时，核心DP思想不变，但需要根据题目要求调整状态定义和转移方程。