【忍者算法】从股市走势到动态规划：探索最大子数组和问题｜LeetCode 53 最大子数组和
从股市走势到动态规划：探索最大子数组和问题生活中的算法
想象你是一位股票交易员，手上有一支股票的每日涨跌数据。你想找出哪段连续的交易日能获得最大的收益。如果某天股票上涨5元，我们记为+5，下跌3元记为-3。找出总和最大的一段连续交易日，就是在寻找最大子数组和。
这个问题在现实生活中很常见。比如分析用户活跃度的波动趋势，研究气温变化的最大累积效应，或是评估企业连续几个月的盈利表现。
问题描述
LeetCode第53题"最大子数组和"是这样描述的：给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
例如：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 的和最大，为 6。最直观的解法：暴力枚举
最容易想到的方法是：枚举所有可能的子数组，计算它们的和，找出最大值。
让我们用一个简单的例子来理解：
nums = 检查子数组 ：和为1检查子数组 ：和为-1检查子数组 ：和为2检查子数组 ：和为1检查子数组 [-2]：和为-2...依此类推找到最大和为3，对应子数组优化解法：动态规划
仔细思考会发现，我们在计算每个位置结尾的最大子数组和时，只需要关注前一个位置的最大子数组和是否值得接续。
类似继承资产，如果之前继承的是正资产，不管多还是少，有总比没有好。我在之前的资产基础上，加上我目前的资产或者负债。
可要是之前继承的是一笔负债，那我宁可不要，选择白手起家。
动态规划的原理
[*]定义dp为以第i个数结尾的最大子数组和
[*]如果前面的和是正数，就值得接续；如果是负数，就重新开始
[*]状态转移方程：dp = max(dp + nums, nums)
[*]最终答案是dp数组中的最大值
算法步骤演示
用nums = 演示这个过程：
1. 处理1：dp = 1当前最大和 = 12. 处理-2：dp = max(1-2, -2) = -1当前最大和 = 13. 处理3：dp = max(-1+3, 3) = 3当前最大和 = 34. 处理-1：dp = max(3-1, -1) = 2最终最大和 = 3Java代码实现
public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { return 0; } // dp表示以i结尾的最大子数组和 int[] dp = new int; dp = nums; int maxSum = dp; for (int i = 1; i < nums.length; i++) { // 状态转移：要么接续前面的和，要么重新开始 dp = Math.max(dp + nums, nums); // 更新全局最大和 maxSum = Math.max(maxSum, dp); } return maxSum;}进一步优化：空间优化
观察发现，我们其实只需要前一个状态的值，不需要保存整个dp数组。
public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int currentMax = nums; int maxSum = nums; for (int i = 1; i < nums.length; i++) { currentMax = Math.max(currentMax + nums, nums); maxSum = Math.max(maxSum, currentMax); } return maxSum;}解法比较
让我们比较这些解法：
暴力枚举：
[*]时间复杂度：O(n²)
[*]空间复杂度：O(1)
[*]优点：直观易懂
[*]缺点：效率较低
动态规划：
[*]时间复杂度：O(n)
[*]空间复杂度：O(n)
[*]优点：高效且易于理解
[*]缺点：需要额外空间
空间优化版：
[*]时间复杂度：O(n)
[*]空间复杂度：O(1)
[*]优点：时空效率都很高
[*]缺点：代码不如dp数组版直观
扩展思考
这道题目启发我们：
[*]当遇到"最大"/"最小"类型的问题时，考虑动态规划
[*]寻找问题中的递推关系
[*]关注是否可以优化空间复杂度
[*]注意处理负数的情况
类似的问题还有：
[*]买卖股票的最佳时机
[*]乘积最大子数组
[*]环形子数组的最大和
小结
通过最大子数组和这道题，我们不仅学会了一个经典的动态规划问题的解法，更重要的是理解了如何将复杂问题分解为子问题，并利用子问题的解构建最终答案。这种思维方式在解决其他动态规划问题时也会很有帮助。
记住，当遇到需要求解"最大连续和"类型的问题时，动态规划往往能提供一个优雅而高效的解决方案！
<hr>作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～
页:
[1]