线性动态规划：最大子数组和 题目描述 给定一个整数数组 nums ，请找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。例如，输入 nums = [-2,1,-3,4,-1,2,1,-5,4] ，连续子数组 [4,-1,2,1] 的和最大，为 6。 解题思路 问题分析 ：目标是找到连续子数组的最大和。暴力枚举所有子数组需要 O(n²) 时间，而动态规划可以将时间复杂度优化到 O(n)。 关键观察 ：对于以第 i 个元素结尾的子数组，其最大和只有两种可能： 单独包含 nums[i] ； 或接在以 i-1 结尾的子数组之后（即 dp[i-1] + nums[i] ）。 状态定义 ：设 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。 状态转移方程 ： \[ dp[ i] = \max(nums[ i], \ dp[ i-1] + nums[ i ]) \] 即，如果 dp[i-1] > 0 ，则接上前面的子数组；否则从 nums[i] 重新开始。 最终答案 ：所有 dp[i] 中的最大值，因为最大和子数组可能以任意位置结尾。 逐步求解示例 以 nums = [-2,1,-3,4,-1,2,1,-5,4] 为例： 初始化： dp[0] = -2 ，全局最大值 max_sum = -2 。 i=1 ： dp[1] = max(1, -2+1) = max(1, -1) = 1 ， max_sum = max(-2, 1) = 1 。 i=2 ： dp[2] = max(-3, 1-3) = max(-3, -2) = -2 ， max_sum 仍为 1。 i=3 ： dp[3] = max(4, -2+4) = 4 ， max_sum = 4 。 i=4 ： dp[4] = max(-1, 4-1) = 3 ， max_sum = 4 。 i=5 ： dp[5] = max(2, 3+2) = 5 ， max_sum = 5 。 i=6 ： dp[6] = max(1, 5+1) = 6 ， max_sum = 6 。 后续计算不会超过 6，最终结果为 6 。 优化 实际只需维护前一个状态的 dp 值和一个变量记录最大值，空间复杂度可降至 O(1)。