题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例
示例 1：
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
解答方法
方法一：动态规划
思路
首先，对于数组中的第i个数，它的状态有两种：(a)nums[i] 在最大子序中；(b)nums[i]不在最大子序中。
dp[i]表示nums中以nums[i]结尾的最大子序和,在分析第i个数时，前i-1个数已经达到最优解，最优解时，用dp[i-1]表示第i-1个数的状态。
res为dp中最大的数
代码
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
dp[0] = nums[0]
res = dp[0]
for i in range(1,len(nums)):
dp[i] = max(nums[i],dp[i-1]+nums[i])
res = max(res, dp[i])
return res
时间复杂度
O(n)
空间复杂度
方法二：贪心
思路
从左往右遍历，一个个数字加过去，如果sum<0,重新开始找子序串
代码
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res = nums[0]
sum = 0
for num in nums:
sum += num
res = max(res, sum)
if sum < 0:
sum = 0
return res
时间复杂度
O(n)
空间复杂度
O(1)
