Python Greedy Solution

  • 5
    def maxSubArray(self, A):
        current = 0
        result = A[0]
        for i in A:
            current += i
            result = max(current,result)
            current = max(0,current)
        return result

    The idea is that as long as long as you're above 0, you've retained the "biggest number" somewhere along the line. once you go below 0 the chain can no longer be the best chain so reset it. Should be pretty easy to follow. O(n) complexity, so obviously not the most optimal, but 76ms.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.