53 Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
The Idea: Only negative elements hurt. As the array get accumulated, if the current sum continues to remain positive, then there is potential for it exceed the current maximum. An otherwise negative element will pull us backwards.
Complexity: O(n) time and O(1) space
import sys
class Solution:
def maxSubArray(self, nums):
:type nums: List[int]
:rtype: int
if not nums: return 0
the_max = -sys.maxsize
cur_sum = 0
for num in nums:
cur_sum += num
the_max = max(the_max, cur_sum)
if cur_sum < 0:
cur_sum = 0
return the_max