Kadane's algorithm for the maximum sub-array problem

Kadanes.py

def max_subarray(A):
    # (maximum sum, max sum start idx, max sum end idx)
    result = (-float('inf'), 0, 0)
    current_max_sum = 0
    current_start_idx = 1
    for i in range(0, len(A)):
        current_max_sum = current_max_sum + A[i]
        if current_max_sum > result[0]:
            result = (current_max_sum, current_start_idx, i)
            
        # If the total contribution of the previous current_start_idx - i elems
        # is 0, it is not a part of the max subarray, so we know it occurs
        # somewhere in A[i+1...len(A)] if at all.
        if current_max_sum < 0:
            current_max_sum = 0
            current_start_idx = i + 1
    return result

if __name__=='__main__':
    A = [2, -3, 1, -5, 8, 10]
    print max_subarray(A) # Result of above = (18, 4, 5)