LeetCode最大数字范围的整数之和

LeetCode最大数字范围的整数之和引言从一道面试题说起在算法面试中有一类问题看似简单却暗藏玄机——「最大数字范围的整数之和」。我第一次遇到这个问题时以为只是简单的数组求和结果被面试官追问了三个优化版本才勉强通过。今天我们就来彻底拆解这道题不仅让你看懂解法更让你理解背后的优化思维。## 问题描述到底要我们做什么假设你有一组整数比如[3, 1, 4, 1, 5, 9, 2, 6]。现在你需要找出连续子数组中和最大的那个。这里的「连续」是关键——不能跳过中间的数字。例如- 子数组[3, 1, 4]的和是 8- 子数组[4, 1, 5, 9]的和是 19- 子数组[9, 2, 6]的和是 17那么最大和就是 19来自[4, 1, 5, 9]。这个问题的官方名称是「最大子数组和」在 LeetCode 上编号 53。它看似简单但暴力解法的时间复杂度是 O(n³)而最优解只需要 O(n)。## 暴力解法最直接但最慢的思路新手最容易想到的方法是枚举所有可能的子数组计算每个子数组的和然后找到最大值。这就像你在一堆数字里把所有可能的连续片段都试一遍。pythondef max_subarray_sum_bruteforce(nums): 暴力解法枚举所有子数组 时间复杂度 O(n³) n len(nums) max_sum float(-inf) # 初始化为负无穷 # 枚举所有可能的起始位置 for i in range(n): # 枚举所有可能的结束位置 for j in range(i, n): # 计算子数组 nums[i:j1] 的和 current_sum 0 for k in range(i, j 1): current_sum nums[k] # 更新最大值 max_sum max(max_sum, current_sum) return max_sum# 测试test_nums [-2, 1, -3, 4, -1, 2, 1, -5, 4]print(f暴力解法结果{max_subarray_sum_bruteforce(test_nums)}) # 输出 6这个代码能正确运行但效率极低。当数组有 1000 个元素时需要执行约 1.67 亿次操作。面试官看到这个解法通常会问「能不能优化」## 动态规划思想把大问题拆成小问题真正的高手会这样思考我们不需要每次都重新计算子数组的和。假设我们已经知道了以nums[i-1]结尾的最大子数组和那么以nums[i]结尾的最大子数组和只有两种可能1. 只包含nums[i]自身2. 包含nums[i]以及前面的最大子数组这就像你是一个贪心的商人如果前面赚的钱是正数你就合并如果是负数你就重新开始。pythondef max_subarray_sum_dp(nums): 动态规划解法利用状态转移 时间复杂度 O(n)空间复杂度 O(n) n len(nums) if n 0: return 0 # dp[i] 表示以 nums[i] 结尾的最大子数组和 dp [0] * n dp[0] nums[0] # 第一个元素只能是自己 max_sum dp[0] for i in range(1, n): # 核心转移方程要么取自己要么取自己前面最大 dp[i] max(nums[i], dp[i-1] nums[i]) # 更新全局最大值 max_sum max(max_sum, dp[i]) return max_sum# 测试test_nums [-2, 1, -3, 4, -1, 2, 1, -5, 4]print(f动态规划解法结果{max_subarray_sum_dp(test_nums)}) # 输出 6这个解法的时间复杂度降到了 O(n)空间复杂度也是 O(n)。面试官会满意吗可能还不够因为我们可以把空间复杂度优化到 O(1)。## 终极优化Kadane 算法Kadane 算法的精髓在于我们根本不需要记录所有以 i 结尾的最大和只需要记住当前的最大和即可。这就像你跑步时只需要知道当前的速度和累计成绩不需要记住每一秒的细节。pythondef max_subarray_sum_kadane(nums): Kadane 算法空间优化版 时间复杂度 O(n)空间复杂度 O(1) if not nums: return 0 # current_max以当前元素结尾的最大子数组和 # global_max全局最大子数组和 current_max global_max nums[0] for i in range(1, len(nums)): # 如果当前和加上新数字还不如新数字本身就重新开始 current_max max(nums[i], current_max nums[i]) # 更新全局最大值 global_max max(global_max, current_max) return global_max# 测试test_nums [-2, 1, -3, 4, -1, 2, 1, -5, 4]print(fKadane 算法结果{max_subarray_sum_kadane(test_nums)}) # 输出 6# 更复杂的测试test_nums2 [5, 4, -1, 7, 8]print(f第二个测试结果{max_subarray_sum_kadane(test_nums2)}) # 输出 23这个算法只有 5 行核心代码却完美解决了问题。它之所以高效是因为它利用了局部最优 → 全局最优的动态规划思想同时避免了不必要的存储。## 深度思考为什么 Kadane 算法是对的你可能会问为什么current_max max(nums[i], current_max nums[i])这个简单的公式就能找到最优解让我们用数学归纳法来理解-基础情况当 i0 时以 nums[0] 结尾的最大子数组和就是它本身。-归纳步骤假设以 nums[i-1] 结尾的最大子数组和是current_max_prev那么以 nums[i] 结尾的最大子数组和必然包含 nums[i]。如果current_max_prev是负数加上它只会让和变小所以应该舍弃否则应该合并。这个思想在计算机科学中被称为「最优子结构」——大问题的最优解可以由子问题的最优解推导出来。## 实战应用不仅仅是算法题最大子数组和问题在现实中有广泛的应用-股票交易找到连续几天的最大收益-信号处理检测信号中的最强连续片段-机器学习在时间序列数据中寻找模式-生物信息学基因序列中的最大相似区域例如假设你有一支股票每天的价格变化数据想找到连续几天中收益最大的区间这个问题就等价于最大子数组和。## 总结从暴力解法到 Kadane 算法我们走完了「最大数字范围的整数之和」的优化之旅。这个过程教会我们1.暴力解法是理解的起点但不是终点。它能帮我们验证正确性但绝不能用在生产环境。2.动态规划的精髓在于状态转移。找到dp[i]和dp[i-1]的关系就是找到了问题的钥匙。3.Kadane 算法展示了极致优化O(n) 时间、O(1) 空间没有冗余的计算和存储。4.算法思维比代码更重要。当你遇到新问题时先思考「是否有重复计算」「能否用之前的计算结果」。下次在面试中遇到这道题你可以从容地给出 Kadane 算法并解释为什么它是最优解。记住好的代码不是写出来的是思考出来的。