leetcode 53. 最大子数组和

你描述的是解决最大子数组和问题的动态规划方法，也被称为Kadane算法。这种方法通过状态转移方程高效地找到连续子数组的最大和。

方法思路

1. 定义状态：设f(i)表示以第i个元素结尾的连续子数组的最大和。
2. 状态转移：对于每个元素nums[i]，有两种选择：
   • 将其加入前面的子数组，和为f(i-1) + nums[i]。
   • 以自身作为新的子数组起点，和为nums[i]。
     取两者中的较大值作为f(i)，即f(i) = max(f(i-1) + nums[i], nums[i])。
3. 全局最优解：遍历所有f(i)，找出最大值。

优化思路

由于f(i)只依赖于f(i-1)，可以使用一个变量pre来维护当前的f(i-1)，从而将空间复杂度从O(n)优化到O(1)。

算法实现

以下是使用Python实现的Kadane算法：

def maxSubArray(nums):n = len(nums)if n == 0:return 0pre = nums[0]  # 初始化pre为第一个元素max_sum = nums[0]  # 初始化最大和为第一个元素for i in range(1, n):# 更新pre为当前元素和(前一个状态+当前元素)中的较大值pre = max(nums[i], pre + nums[i])# 更新全局最大和max_sum = max(max_sum, pre)return max_sum# 示例用法
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums))  # 输出: 6，对应的子数组是[4, -1, 2, 1]

复杂度分析

• 时间复杂度：O(n)，只需遍历数组一次。
• 空间复杂度：O(1)，只需要常数级的额外空间。

这种方法高效且简洁，是解决最大子数组和问题的最优解法。