53. 最大子序和

题目

• 题号：53
• 难度：简单
• https://leetcode-cn.com/problems/maximum-subarray/

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

示例1

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

实现

思路1 动态规划

该题可以使用动态规划的思路解答，维护一个一维数组来记录连续子数组的最大和。而为了节省空间，我们可以直接对输入的nums数组原地修改更新。方法如下：

• 首先需要明确，nums[i]要更新的是到第i个数结尾的连续子数组的最大和。因此nums[0]就是其本身，遍历的时候可以直接从nums[1]开始遍历。
• 然后遍历nums的每个数，当遍历至i时，若pre_sum=nums[i-1]<0，也就是到i-1前的连续子数组的最大和为负，那就直接舍弃这之前的和，连续子数组的和从nums[i]开始记录。因为当nums[i-1]<0时，nums[i-1]+nums[i]<nums[i]，之前的和只会“拖后腿”，不如“重新开始”记录。因此我们发现最优子结构为：max[i] = Max(nums[i-1]+nums[i], nums[i])

  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)
  

  时间复杂度：，其中n为nums数组的长度，我们需要遍历一遍nums数组。
  空间复杂度：.