动态规划 LeetCode 第2题解析

动态规划（Dynamic Programming，简称 DP）是解决许多优化问题的强大工具。下面我将通过一个具体的 LeetCode 题目来解析动态规划的基本思想。

题目描述

给定一个整数数组 nums，返回其最大子数组和。

示例:

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

解题思路

这是一个经典的动态规划问题。我们可以用一个变量 max_sum 来记录到当前位置为止的最大子数组和，并用一个变量 current_sum 来记录当前子数组和。

代码实现

def maxSubArray(nums):
    max_sum = current_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

扩展阅读

想要了解更多动态规划的知识，可以阅读本站的《动态规划基础教程》。