【忍者算法】从股市走势到动态规划：探索最大子数组和问题｜LeetCode 53 最大子数组和

从股市走势到动态规划：探索最大子数组和问题

生活中的算法

想象你是一位股票交易员，手上有一支股票的每日涨跌数据。你想找出哪段连续的交易日能获得最大的收益。如果某天股票上涨5元，我们记为+5，下跌3元记为-3。找出总和最大的一段连续交易日，就是在寻找最大子数组和。
这个问题在现实生活中很常见。比如分析用户活跃度的波动趋势，研究气温变化的最大累积效应，或是评估企业连续几个月的盈利表现。
问题描述

LeetCode第53题"最大子数组和"是这样描述的：给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
例如：

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

复制代码

最直观的解法：暴力枚举

最容易想到的方法是：枚举所有可能的子数组，计算它们的和，找出最大值。
让我们用一个简单的例子来理解：

1. nums = [1,-2,3,-1]
2. 检查子数组 [1]：和为1
3. 检查子数组 [1,-2]：和为-1
4. 检查子数组 [1,-2,3]：和为2
5. 检查子数组 [1,-2,3,-1]：和为1
6. 检查子数组 [-2]：和为-2
7. ...依此类推
8. 找到最大和为3，对应子数组[3]

复制代码

优化解法：动态规划

仔细思考会发现，我们在计算每个位置结尾的最大子数组和时，只需要关注前一个位置的最大子数组和是否值得接续。
类似继承资产，如果之前继承的是正资产，不管多还是少，有总比没有好。我在之前的资产基础上，加上我目前的资产或者负债。
可要是之前继承的是一笔负债，那我宁可不要，选择白手起家。
动态规划的原理

• 定义dp为以第i个数结尾的最大子数组和
  
• 如果前面的和是正数，就值得接续；如果是负数，就重新开始
  
• 状态转移方程：dp = max(dp[i-1] + nums, nums)
  
• 最终答案是dp数组中的最大值
  

算法步骤演示

用nums = [1,-2,3,-1]演示这个过程：

1. 1. 处理1：
2. dp[0] = 1
3. 当前最大和 = 1
5. 2. 处理-2：
6. dp[1] = max(1-2, -2) = -1
7. 当前最大和 = 1
9. 3. 处理3：
10. dp[2] = max(-1+3, 3) = 3
11. 当前最大和 = 3
13. 4. 处理-1：
14. dp[3] = max(3-1, -1) = 2
15. 最终最大和 = 3

复制代码

Java代码实现

1. public int maxSubArray(int[] nums) {
2.     if (nums == null || nums.length == 0) {
3.         return 0;
4.     }
5.    
6.     // dp[i]表示以i结尾的最大子数组和
7.     int[] dp = new int[nums.length];
8.     dp[0] = nums[0];
9.     int maxSum = dp[0];
10.    
11.     for (int i = 1; i < nums.length; i++) {
12.         // 状态转移：要么接续前面的和，要么重新开始
13.         dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
14.         // 更新全局最大和
15.         maxSum = Math.max(maxSum, dp[i]);
16.     }
17.    
18.     return maxSum;
19. }

复制代码

进一步优化：空间优化

观察发现，我们其实只需要前一个状态的值，不需要保存整个dp数组。

1. public int maxSubArray(int[] nums) {
2.     if (nums == null || nums.length == 0) {
3.         return 0;
4.     }
5.    
6.     int currentMax = nums[0];
7.     int maxSum = nums[0];
8.    
9.     for (int i = 1; i < nums.length; i++) {
10.         currentMax = Math.max(currentMax + nums[i], nums[i]);
11.         maxSum = Math.max(maxSum, currentMax);
12.     }
13.    
14.     return maxSum;
15. }

复制代码

解法比较

让我们比较这些解法：
暴力枚举：

• 时间复杂度：O(n²)
  
• 空间复杂度：O(1)
  
• 优点：直观易懂
  
• 缺点：效率较低
  

动态规划：

• 时间复杂度：O(n)
  
• 空间复杂度：O(n)
  
• 优点：高效且易于理解
  
• 缺点：需要额外空间
  

空间优化版：

• 时间复杂度：O(n)
  
• 空间复杂度：O(1)
  
• 优点：时空效率都很高
  
• 缺点：代码不如dp数组版直观
  

扩展思考

这道题目启发我们：

• 当遇到"最大"/"最小"类型的问题时，考虑动态规划
  
• 寻找问题中的递推关系
  
• 关注是否可以优化空间复杂度
  
• 注意处理负数的情况
  

类似的问题还有：

• 买卖股票的最佳时机
  
• 乘积最大子数组
  
• 环形子数组的最大和
  

小结

通过最大子数组和这道题，我们不仅学会了一个经典的动态规划问题的解法，更重要的是理解了如何将复杂问题分解为子问题，并利用子问题的解构建最终答案。这种思维方式在解决其他动态规划问题时也会很有帮助。
记住，当遇到需要求解"最大连续和"类型的问题时，动态规划往往能提供一个优雅而高效的解决方案！
作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！