给定一个整数数组，找出总和最大的连续数列，并返回总和。

示例：

输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。

示例代码1（动态规划）：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        sum = [0] * n
        tmp = 0
        for i in range(n):
            tmp = max(tmp + nums[i], nums[i])
            sum[i] = tmp
        return max(sum)

示例代码2（贪心算法）：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        ret = float('-inf')
        tmp = 0
        for i in range(n):
            tmp += nums[i]
            if tmp < nums[i]:
                tmp = nums[i]
            ret = max(ret, tmp)
        return ret