这道题目最直观的做法是枚举数组的所有子数组并求出它们的和，但是对于一个长度为n的数组来说，总共有n（n+1）/2 个子数组，时间复杂度为O（N^2）。所以讨论另外两个更优的解法。
解法一，举例分析数组的规律。以数组[1, -2, 3, 10, -4, 7, 2, -5]为例，从头到尾逐个累加。先初始化和为0，第一步加上数字1，此时和为1。第二步加上数字-2，和就变成了-1。第三步加上数字3。我们注意到由于此前累加的和是-1，小于0，那如果用3加上-1，得到的和为2，比3本身还小，也就是说，从第一个数字开始考虑的子数组的和会小于从第三个数字开始的子数组和。因此我们不用去考虑从第一个数字开始的子数组，之前累加的和也被抛弃。我们从第三个数字重新开始累加，此时和为3。第四步加10，得到的和为13。第五步加上-4，和为9。我们注意到，由于-4是一个负数，因此累加-4后得到的和比原来的和还要小，因此，我们要把之前得到的13给保存下来，因为它有可能是最大的子数组和。第六步加上7，我们得到16，我们把最大的子数组和更新为16。第七步再加2，将最大子数组和更新为18。第八步加上最后一个数字-5，由于得到的和为13，小于此前最大的和18，因此，最终的子数组的和为18，对应的子数组为[3, 10, -4, 7, 2]。按照在这个过程中发现的规律，我们可以将代码写出来，如1所示。这个算法的时间复杂度是O（N），空间复杂度是O（1）。
另外，我们也可以用动态规划的思想解决该题。如果我们用函数f（i）表示以第i个数字结尾的子数组的最大和，那么我们需要求出max[f(i)]，其中0<=i < n。那么，我们可以用递归公示求f（i），当i=0或f（i-1）<=0时，f（i）就是数组中的第i个数字，如同上面的前面子数组和为负数的情况；如果i！=0并且f（i-1）> 0时，f（i）= f（i-1）+ nums[i]。虽然我们用递归的方式分析动态规划的问题，但最终都会基于循环去编码，这样写出来的代码是和上诉的思路写出的代码相同的。
class Solution:
def maxSubArray1(self, nums: List[int]) -> int:
cursum, greatestsum = 0, float("-inf")
for i in range(len(nums)):
if cursum < 0:
cursum = nums[i]
else:
cursum += nums[i]
if cursum > greatestsum:
greatestsum = cursum
return greatestsum