LeetCode 53. Maximum Subarray 题解
LeetCode 53. Maximum Subarray 题解
题目描述
给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：
输入：nums = [1] 输出：1示例 3：
输入：nums = [5,4,-1,7,8] 输出：23解题思路
方法：动态规划
思路：
- 定义
dp[i]为以nums[i]结尾的最大子数组和 - 状态转移方程：
dp[i] = max(nums[i], dp[i-1] + nums[i])，即要么当前元素自己作为一个子数组，要么与前面的子数组合并 - 最终结果为
max(dp)
复杂度分析：
- 时间复杂度：O(n)，其中 n 是数组的长度。只需要遍历数组一次。
- 空间复杂度：O(n)，需要一个长度为 n 的数组来存储状态。
方法：动态规划（空间优化）
思路：
- 观察到
dp[i]只依赖于dp[i-1]，因此可以使用一个变量来存储前一个状态，不需要使用数组 - 初始化
current_sum为nums[0]，max_sum为nums[0] - 遍历数组从第二个元素开始：
current_sum = max(nums[i], current_sum + nums[i])max_sum = max(max_sum, current_sum)
复杂度分析：
- 时间复杂度：O(n)，其中 n 是数组的长度。只需要遍历数组一次。
- 空间复杂度：O(1)，只需要常数级的额外空间。
代码实现
方法：动态规划
class Solution: def maxSubArray(self, nums: List[int]) -> int: n = len(nums) if n == 0: return 0 dp = [0] * n dp[0] = nums[0] for i in range(1, n): dp[i] = max(nums[i], dp[i-1] + nums[i]) return max(dp)方法：动态规划（空间优化）
class Solution: def maxSubArray(self, nums: List[int]) -> int: n = len(nums) if n == 0: return 0 current_sum = nums[0] max_sum = nums[0] for i in range(1, n): current_sum = max(nums[i], current_sum + nums[i]) max_sum = max(max_sum, current_sum) return max_sum测试用例
测试用例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
测试用例 2：
输入：nums = [1]
输出：1
测试用例 3：
输入：nums = [5,4,-1,7,8]
输出：23
测试用例 4：
输入：nums = [-1,-2,-3,-4]
输出：-1
总结
本题是动态规划的经典问题，主要考察对状态定义和状态转移方程的理解。两种方法各有特点：
- 动态规划：代码清晰易懂，逻辑明确，但需要 O(n) 的空间。
- 动态规划（空间优化）：空间复杂度为 O(1)，更高效，适用于大规模数据。
在实际应用中，空间优化的方法通常是首选，因为它不仅空间效率高，而且代码简洁。
这种方法不仅适用于最大子数组和问题，还可以应用于许多其他需要动态规划解决的问题，例如最大乘积子数组、最长递增子序列等。掌握动态规划的思想，对于解决这类问题非常重要。