题目链接：点击这里

1.动态规划

思路：令状态 表示以 作为末尾的连续序列的最大和（即 必须作为连续序列的末尾）

通过这个 数组，要求的最大子序和其实就是 中的最大值 。

现作如下考虑：因为 要求是必须以 结尾的连续序列，那么只有两种情况：

1. 这个最大和的连续序列只有一个元素，即以 开始，以 结尾。
2. 这个最大和的连续序列有多个元素，即从前面某处 开始 ，一直到 结尾。

对第1种情况，最大和就是 本身。

对第2种情况，最大和是 ，即 。

于是得到状态转移方程：，其中

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n

        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(nums[i], dp[i - 1] + nums[i])
        
        return max(dp)

空间优化：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        premax = ans = nums[0]
        for i in range(1, n):
            premax = premax + nums[i] if premax > 0 else nums[i]
            ans = max(ans, premax)
        return ans

2.分治

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        return self.calc(nums, 0, n - 1)
    
    def calc(self, nums:List[int], l:int, r:int) -> int:
        if l == r:
            return nums[l]
        
        mid = (l + r) // 2
        
        left = self.calc(nums, l, mid)
        right = self.calc(nums, mid + 1, r)
        
        lmax, lsum = nums[mid], 0
        for i in range(mid, l - 1, -1):
            lsum += nums[i]
            lmax = max(lmax, lsum)
        
        rmax, rsum = nums[mid + 1], 0
        for i in range(mid + 1, r + 1):
            rsum += nums[i]
            rmax = max(rmax, rsum)
        
        return max(left, right, lmax + rmax)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        return Solution.calc(self, nums, 0, n - 1)
    
    def calc(self, nums:List[int], l:int, r:int) -> int:
        if l == r:
            return nums[l]
        
        mid = (l + r) // 2
        
        left = Solution.calc(self, nums, l, mid)
        right = Solution.calc(self, nums, mid + 1, r)
        
        lmax, lsum = nums[mid], 0
        for i in range(mid, l - 1, -1):
            lsum += nums[i]
            lmax = max(lmax, lsum)
        
        rmax, rsum = nums[mid + 1], 0
        for i in range(mid + 1, r + 1):
            rsum += nums[i]
            rmax = max(rmax, rsum)
        
        return max(left, right, lmax + rmax)

Python类中方法相互调用的两种方式：

1. 类名.方法名(self)
   注意：方法名内必须传入一个实例对象的指针，self后可根据方法定义放入适当实参

2. self.方法名(方法列表)
   方法列表不应该包括self