最大子数组和（Maximum Subarray Sum） 题目描述 给定一个整数数组 nums ，请你找出其中 连续子数组 的和的最大值，并返回这个最大值。 示例： 输入：nums = [ -2,1,-3,4,-1,2,1,-5,4 ] 输出：6 解释：连续子数组 [ 4,-1,2,1 ] 的和最大，为 6。 解题思路 这是一个经典的线性动态规划问题，核心思想是：以每个位置结尾的“最大子数组和”只依赖于前一个位置的“最大子数组和”。 定义状态： dp[i] 表示以第 i 个元素结尾的连续子数组的最大和。 状态转移： 如果 dp[i-1] > 0 ，那么把 nums[i] 接在后面能使和更大，即 dp[i] = dp[i-1] + nums[i] 。 如果 dp[i-1] ≤ 0 ，那么从 nums[i] 重新开始更优，即 dp[i] = nums[i] 。 最终答案就是所有 dp[i] 中的最大值。 详细步骤 初始化 设 dp[0] = nums[0] ，因为第一个元素只能单独成为子数组。 同时用 maxSum = nums[0] 记录全局最大值。 状态转移 遍历 i 从 1 到 n-1： 如果 dp[i-1] > 0 ，则 dp[i] = dp[i-1] + nums[i] 。 否则 dp[i] = nums[i] 。 更新 maxSum = max(maxSum, dp[i]) 。 空间优化 由于 dp[i] 只依赖于 dp[i-1] ，我们可以只用变量 curSum 代替整个数组： 初始 curSum = nums[0] ， maxSum = nums[0] 。 遍历 i=1 到 n-1： 如果 curSum > 0 ，则 curSum = curSum + nums[i] 。 否则 curSum = nums[i] 。 更新 maxSum = max(maxSum, curSum) 。 举例 nums = [ -2,1,-3,4,-1,2,1,-5,4 ] i=0: curSum=-2, maxSum=-2 i=1: curSum>0? 否，curSum=1, maxSum=1 i=2: curSum>0? 是，curSum=1+(-3)=-2, maxSum=1 i=3: curSum>0? 否，curSum=4, maxSum=4 i=4: curSum>0? 是，curSum=4+(-1)=3, maxSum=4 i=5: curSum>0? 是，curSum=3+2=5, maxSum=5 i=6: curSum>0? 是，curSum=5+1=6, maxSum=6 i=7: curSum>0? 是，curSum=6+(-5)=1, maxSum=6 i=8: curSum>0? 是，curSum=1+4=5, maxSum=6 最终结果：6。 复杂度分析 时间复杂度：O(n)，只需一次遍历。 空间复杂度：O(1)，只用了常数变量。 扩展思考 如果数组为空，可以返回 0 或一个极小值，具体看题目要求。此解法是 Kadane 算法的简化形式，是许多子数组问题的基础。