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

Kadane算法

• 算法描述：
  • 遍历该数组， 在遍历过程中， 将遍历到的元素依次累加起来， 当累加结果小于或等于0时， 从下一个元素开始，重新开始累加。
  • 累加过程中， 要用一个变量(max_so_far)记录所获得过的最大值
  • 一次遍历之后， 变量 max_so_far 中存储的即为最大子片段的和值。

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
sum = 0
max_so_far = nums[0]
for num in nums:
sum += num
if sum > max_so_far:
max_so_far = sum
if sum < 0:
sum = 0
return max_so_far

该问题最初由布朗大学的Ulf Grenander教授于1977年提出，不久之后卡内基梅隆大学的Jay Kadane提出了该问题的线性算法。

https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%AD%90%E6%95%B0%E5%88%97%E9%97%AE%E9%A2%98

真卡蛋。