对于许多这样的问题，都有一个标准的逻辑，假设你知道nums[:n - 1]是一个具有最大总和的子数组，那么对于nums[:n]，你能找到的具有最大总和的子数组是什么？
有两种可能性：

• 新答案不包含nums[n-1]。在这种情况下，它必须与旧答案相同
• 新答案 * 不 * 包含nums[n-1]。

所以......实际的算法是迭代遍历数组，反复向数组中添加新元素，并跟踪两个答案：
1.总数最大的子数组是什么
1.包含最后一个元素的最大总和的子数组是什么？（这个答案可能和前面的相同。）
当您随后将新元素添加到数组末尾时：
1.具有最大总计的子数组是（a）以前的最大总计，或（b）以前的最大总计（包含最后一个元素加上新的最后一个元素），或（c）只是最后一个元素。选择具有最大总计的子数组。
1.包含最后一个元素的总和最大的子数组是上述（b）或（c）中较大的一个。

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

这是具有恒定空间的2遍O(n)时间复杂度解。
工作原理：我们把每个元素加到它的前趋元素上，前提是前趋元素大于0（大于或等于也可以）。如果负数已经设法使它小于0，我们就丢弃前缀，不再关心它们;但如果还有一些正值，我们就加上它，因为它总比没有好。
最后我们寻找最大值。
要使它成为一个循环，你只需有一个best值，在每次迭代时取max，这样你就不需要在数组末尾再次循环取max。
这是顺便说一句，Kadane的算法，如果你有兴趣进一步阅读它。

下面是我的解决方案，虽然当输入列表有很多元素时会超过时间限制。我的想法是尝试每个子列表的总和，并相应地更新最大总和。有一个更快，但更复杂的方法是使用“分治”方法：https://leetcode.com/problems/maximum-subarray/discuss/1849465/Divide-and-Conquer-Approach-with-Python
我的解决方案（由于Time Limit Exceeded，适用于200/209种情况）：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = - 10 ** 4

        for i in range(len(nums)):
            for j in range(i + 1, len(nums) + 1):
                s = sum(nums[i:j])
                if max_sum < s:
                    max_sum = s
        return max_sum

你可以使用Kadane算法在O(n)时间和空间（以及恒定的额外空间）内求解problem，这是一个简单的动态编程算法：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = -10**4
        current_sum = 0
        
        for n in nums:
            current_sum = n if n > current_sum+n else current_sum+n
            if current_sum > max_sum:
                max_sum = current_sum
        return max_sum