53. 最大子序和

一、题目

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

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

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

二、思路

1. 动态规划

我们假设i为和最大的子序列的结束位置，用 ai 表示 nums[i]。然后我们可以用一个数组dp来保存这些结果，然后求dp数组中的最大值即可。即：
$$
max(dp)
$$
因此，我们需要求出数组dp中每一个位置。而dp[i]的值又与dp[i-1]有关，这取决于dp[i]**与dp[i-1] + ai**谁大谁小，最后我们取一个较大者。所以，可以得出状态转移方程：
$$
dp[i] = max(dp[i-1] + ai, ai)
$$
对于这道题呢，我们实际上就不需要新设一个数组了，直接将每次计算结果保存到nums中i对应位置即可。

在计算之前我们还需要进行一些条件限定：

• 首先，0 <= i <= len(nums)
• 其次，如果nums长度小于等于1，那么就不需要判断了，直接返回即可，所以我们可以直接从1开始。

三、代码

1. 动态规划

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] = max(nums[i-1] + nums[i], nums[i])
        return max(nums)

四、表现

method	运行时间	表现	内存消耗	表现
1.动态规划	52ms	57.45%	14.4MB	5.01%