动态规划（Dynamic Programming，简称 DP）是解决某些优化问题的有效方法。LeetCode 上的 DP 问题多种多样，本教程将探讨 LeetCode DP 3 的解题思路。

题目描述

假设你有一个数组 nums，请你找出该数组中所有连续子数组的最大和。

例如，给定 nums = [1, -3, 2, 1, -1]，你需要找出连续子数组的最大和。

解题思路

这是一个经典的 DP 问题，可以通过以下步骤解决：

  1. 初始化：定义一个变量 max_sum 用来存储当前已知最大子数组的和。
  2. 遍历：遍历数组中的每个元素，计算以当前元素为结尾的连续子数组的和。
  3. 更新：每次计算完成后，更新 max_sum。
  4. 返回：遍历结束后，max_sum 即为所有连续子数组的最大和。

示例代码

以下是一个使用 Python 编写的示例代码：

def maxSubArray(nums):
    max_sum = float('-inf')
    current_sum = 0
    for num in nums:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

nums = [1, -3, 2, 1, -1]
print(maxSubArray(nums))  # 输出：3

扩展阅读

想要了解更多关于动态规划的知识，可以阅读 LeetCode 动态规划专题。

动态规划图解

以上就是对 LeetCode DP 3 的解题思路的简要介绍，希望对你有所帮助！