def kadanesAlgorithm(array):
    max_sum = array[0]
    max_ending_here = array[0]
    for num in array[1:]:
        max_ending_here = max(num, max_ending_here + num)
        max_sum = max(max_sum, max_ending_here)
    return max_sum

df170af32b42f1162de5526726647895d1d1eabc
<mask token>

def kadanesAlgorithm(array):
    max_sum = array[0]
    max_ending_here = array[0]
    for num in array[1:]:
        max_ending_here = max(num, max_ending_here + num)
        max_sum = max(max_sum, max_ending_here)
    return max_sum
