1.题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
2. 分析
- 这是一个动态规划问题
- 我第一步想到的是用两个指针
left和right分别指向最大子序的头和尾，但是有一个空间复杂度会很高，你要保存这两个指针并且保存其所代表的序列的和，然后再和后续的进行判断 - 后面没有去写这个算法，想到一个更为金边，因为题目只要求返回和，那么就是一个比较简单的动态规划问题，可以直接判断
nums[i]和nums[i] + nums[i - 1]之间的大小，并将大的数赋值给nums[i]，这样就实现了一个不断寻找最大值的一个过程。
3.解答
class Solution:
def maxSubArray(self, nums) -> int:
if not nums or len(nums) == 1:
return nums[0]
ans = nums[0]
for i in range(1, len(nums)):
nums[i] = max(nums[i] + nums[i - 1], nums[i])
ans = max(ans, nums[i])
return ans
