leetcode: 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.
#
# click to show more practice.
#
# 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.

class Solution():
    def maxSubArray(self, x):
        if not x:
            return 0
        curSum = maxSum = x[0]
        for ele in x[1:]:
            curSum = max(ele, curSum+ele)
            maxSum = max(maxSum, curSum)
        return maxSum


if __name__ == "__main__":
    assert Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) == 6