def maxSubArray(self, A): current = 0 result = A 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.