class Solution:
    '''
    Time Complexity: O(n)
    Space Complexity: O(1)
    Where, n is number of elements in the given array.
    This is Kadane's Algorithm, this is the most efficient solution for this problem.
    '''
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = -100000
        curSum = 0
        for n in nums:
            curSum += n
            maxSum = max(maxSum, curSum)
            if curSum < 0:
                curSum = 0
        return maxSum