Leetcode 53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

The solution is simple but not very easy to get: once the sum is less than 0, abandon it.

Solution:

# T:O(n) S:O(1)
class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def maxSubArray(self, nums):
        thisSum, maxSum = 0, -999
        for i in xrange(len(nums)):
            if thisSum < 0:
                thisSum = 0
            thisSum += nums[i]
            maxSum = max(thisSum, maxSum)
        return maxSum

Run Time: 56 ms