Python Greedy Solution


  • 5
    J
    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.