最大子数组和-LeetCode

53. 最大子数组和-LeetCode

🎯 问题描述（来源于LeetCode）

描述：给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

说明：

• 子数组是数组中的一个连续部分。

• 示例：

  • 示例 1：

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

  • 示例 2：

  输入：nums = [1]
  输出：1

💻 解题思路

思路1：动态规划 (Kadane算法)

核心思想：
这道题的关键在于**“局部最优”导致“全局最优”。
我们不需要关心整个数组怎么切分，只需要关注：“如果我要以当前位置 i 结尾，我能得到的最大和是多少？”**

1. 状态定义：dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。
2. 贪心策略（状态转移）：
   • 当我们走到 nums[i] 时，我们面临两个选择：
     • 加入前面的队伍：如果前面的 dp[i-1] 是正数（有利可图），那就加上它。
     • 另起炉灶：如果前面的 dp[i-1] 是负数（它是累赘），那不如抛弃它，从 nums[i] 重新开始。
   • 公式：dp[i] = max(nums[i], dp[i-1] + nums[i])。
3. 结果：dp 数组中的最大值即为答案（因为最大子数组不一定以最后一个元素结尾）。

算法步骤：

1. 初始化 dp 数组，dp[0] = nums[0]。
2. 从 i = 1 开始遍历数组。
3. 根据 dp[i-1] 的正负性更新 dp[i]。
4. 遍历 dp 数组，返回最大值。

思路1：代码实现

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        # dp[i] 表示以 nums[i] 结尾的连续子数组的最大和
        dp = [0] * n
        dp[0] = nums[0]
        
        # 状态转移
        for i in range(1, n):
            # 核心逻辑：如果前面的和是负的，就不要了，自己单干
            if dp[i-1] < 0:
                dp[i] = nums[i]
            else:
                # 如果前面的和是正的，就接在它后面
                dp[i] = dp[i-1] + nums[i]
        
        # 返回所有可能中的最大值
        return max(dp)

思路1：📊 性能分析

提交结果

• 运行时间：47 ms (击败 64.43%)
• 内存消耗：31.02 MB (击败 31.62%)

复杂度验证

• • 解析：只需要遍历一次数组。
• • 解析：使用了一个长度为 n 的 dp 数组。
    • 优化提示：其实我们只需要 dp[i-1]，不需要保存整个数组，可以用一个变量 pre_max 代替，将空间复杂度降为 $O(1)$。

思考

1. 为什么是 dp[i-1] < 0 而不是 nums[i-1] < 0？

   • 这是一个常见的误区。我们要判断的是**“前面那一串子数组的总和”**是不是累赘，而不是判断前一个数字是不是负数。
   • 例如：[10, -5, 2]。虽然 -5 是负数，但 10 + (-5) = 5 是正数。对于 2 来说，前面的总和 5 是有帮助的，所以应该接上去。你的代码逻辑 dp[i-1] < 0 完美处理了这种情况。

2. 如何优化空间复杂度到 $O(1)$？

   • 既然 dp[i] 只依赖 dp[i-1]，我们完全可以用一个变量 current_max 来滚动记录，不需要开数组。
   • 这也是这道题的最佳解法（Kadane算法的标准版）：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        current_max = nums[0] # 当前子数组最大和
        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