Kadane's algorithm

kadanes.py

class Solution(object):

    def solve(self, a):

        if not a:
            return 0

        sum_so_far = a[0]
        max_sum = a[0]

        for i in range(1, len(a)):

            if sum_so_far < 0:
                sum_so_far = 0

            sum_so_far += a[i]

            if sum_so_far > max_sum:
                max_sum = sum_so_far

        return max_sum


if __name__ == "__main__":
    a = [2, -1, 2, 3, 4, -5]
    ans = Solution().solve(a)
    print(ans)